CODEWITHSUNDEEP
pythonmathcombinationscombinatorics
David Lopes
David Lopes

Reputation: 46

Python - Combinations only if condition applies

Suppose I have a huge list of tuples:

tuples = ([1, 2], [2, 1], [3, 2], [25, 73], [1, 3]...)

This list has 360000 elements as of now (they are a list of coprimes numbers). I need to make combinations of 3 tuples, such that there are only 3 different numbers on each combination, example:

([2, 1], [3, 1], [3, 2])
([2, 1], [5, 1], [5, 2])

I need to discard combinations with 4 or more different numbers while generating the list of combinations.

If I try to bruteforce this and test each combination, I end up with 360000 choose 3 which is 7.77 * 10^15possible combinations to test.

EDIT: The problem I am trying to solve is:

Find all combinations of coprime pairs in the form:

(a, b), (a, c), (b, c)

for c < 120000

Steps I've taken:

  1. Generate the ternary tree for all Coprime pairs whereboth numbers are less than 120000
  2. (ISSUE - Generate the combinations, bruteforcing it won't do)

Upvotes: 2

Views: 7022

Answers (2)

eumiro
eumiro

Reputation: 212885

Let's make a dict of sets mapping all larger elements to smaller elements within a tuple:

d = {}
for tup in tuples:
    # here you may limit max(tup) to 120000
    d.setdefault(min(tup), set()).add(max(tup))

# {1: {2, 3}, 2: {3}, 25: {73}}

This eliminates also all symetrical pairs: (1, 2), (2, 1).

And then search for all working combinations:

for a, bc in d.iteritems():
    for b, c in it.combinations(sorted(bc), 2):
        if b in d and c in d[b]:
            print(a, b, c) # or yield or append to a list

Should be faster than your brute force…

Upvotes: 5

Charles
Charles

Reputation: 11479

for a in range(1, 120000):
  for b in range(a+1, 120000):
    if (gcd(a, b) > 1):
      continue;
    for c in range(b+1, 120000):
      if (gcd(a, c) = 1 and gcd(b, c) = 1):
        print (a, b, c)

With N = 120000 this takes time roughly N^3/pi^2. A brute force check of all tuples takes time N^6/48, so this is much faster -- about 3 * 10^14 times faster.

Upvotes: 1

Related Questions