Math python question

[Deonvek]

Hello, I'm new to this forum and I have a question. for those who are interested.
If i have a list of number ex: N=[1,2,3,4] and that I also have a list of numbers that cannot be together ex: P=[(1,2),(2,3),(3,4)] is it possible to make a cheap algorithm that won't test all the possible combinations to find a combination that works?

thanks for any response
Deon

[deanhystad]

What do you mean by "cannot be put together" and "works"? Does [(1, 2), (25, 99), (8000, 9999)] work? Are you looking for no duplicates, or do the numbers also have to be sequential like [(1, 2), (3, 4), (5, 6)]? If sequential, do the numbers have to be in the sequential order, or is [(1, 5), (4, 2), (3, 6)] work?

More details please.

[Gribouillis]

You forgot to tell us what is a «combination that works», I suppose it is some set of non adjacent nodes, or a partition of such sets. In that case, a greedy coloring algorithm could help.

[ibreeden]

Deon has two lists: The input list N and a list of forbidden combinations P.
So I guess he wants all permutations of N, but skip forbidden combinations. Am I right @Deonvek ?

An efficient way of comparing values is to use set(). So I would use this for storing forbidden combinations P.

N=[1,2,3,4]
P={(1,2),(2,3),(3,4)} # Make a set of forbidden combinations.

cartesian_product = set()

# You could also use itertools.product to find all permutations.
for i in N:
    for j in N:
        cartesian_product.add((i,j))

print("DEBUG ", cartesian_product)

result = cartesian_product - P
print("RESULT", result)

Output:
DEBUG  {(4, 4), (2, 4), (1, 2), (2, 1), (3, 4), (4, 1), (3, 1), (4, 3), (1, 1), (1, 4), (4, 2), (2, 3), (3, 3), (2, 2), (3, 2), (1, 3)}
RESULT {(2, 4), (2, 1), (4, 3), (3, 1), (2, 2), (3, 2), (4, 1), (1, 3), (4, 4), (1, 1), (1, 4), (4, 2), (3, 3)}

Now this is not exactly what you asked for, because you said:

algorithm that won't test all the possible combinations

Well you would have to test the combination at some point. Will the resultset be too large to fit in memory? Then you will have to skip the forbidden combinations in the nested loop.

[deanhystad]

Does order matter? Is (2, 1) the same as (1, 2)?

Are duplicates such as (1, 1) allowed?

When you say you are looking for a combination that works, what do you mean by "combination"? Are you looking for pairs ((1, 3), (1, 4), (2, 4))?, enough pairs that every number in n is represented ((1, 3), (2, 4))?

Based on what ibreeden says and my guesses, are you looking for something like this:

n = (1, 2, 3, 4)
p = ((1, 2), (2, 3), (3, 4))

# Convert p to dictionary
bad = {a: {a} for a in n}
for a, b in p:
    bad[a].add(b)
    bad[b].add(a)
print("Bad", bad)

# Create a dictionary of numbers that can be paired.
good = {a: [b for b in n if b not in bad[a]] for a in n}
print("Good", good)

# Create all good pairs.  Assumes order is not important: (1, 2) == (2, 1).
# If order matters, leave out "if b > a".
good_pairs = [(a, b) for a, c in good.items() for b in c if b > a]
print("Good pairs", good_pairs)

Output:
Bad {1: {1, 2}, 2: {1, 2, 3}, 3: {2, 3, 4}, 4: {3, 4}}
Good {1: [3, 4], 2: [4], 3: [1], 4: [1, 2]}
Good pairs [(1, 3), (1, 4), (2, 4)]

[lothar]

my interpreation of this task:

from itertools import permutations

res = []
nums = [1,2,3,4]
not_allowed = [(1,2),(2,3),(3,4)]

for perm in permutations(nums,2):
    if perm not in not_allowed:
        res.append(perm)
print(res)

Output:
[(1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)]

[deanhystad]

The op requested a solution that doesn't test all possible combinations. I don't that meant testing more than all possible combinations. On the other hand, your solution does take the order of the pair into account if order is important.