Generate all 4-tuple pairs from n elements

Question

I would like to generate a list of all possible 4-tuple pairs given an array of size n. n is at least 8, so it is always possible to find at least 1 pair.

As an example that helps to understand the problem I use a smaller version of the problem, 2-tuple pairs given an arrayy of size 5. The expected result for 2-tuple pairs would result in 15 items (tuples are ordered, no duplications):

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

My current way in doing this is to use itertools from python and go through all elements returned by itertools.combinations, do 2 loops and find 2 pairs that do not share a single element and then work with that element.

To express this in python code I prepared a small snippet:

arr = list(range(30)) # example list 
comb = list(itertools.combinations(range(0, len(arr)), 4))

for c1 in comb:
    for c2 in comb:  # go through all possible pairs
        if len([val for val in c1 if val in c2]) == 0:  # intersection of both sets results in 0, so they don't share an element
            ... # do something and check for duplicates

This method is doing its job, but is inefficient due to the 2 loops and only works for small n in a given timeframe. Can this be done more efficient?

---

Update: After some answers I evaluated the suggestions. The best thing for my specific case is the (extended) algorithm provided by the (now deleted) answer of MSeifert, which performs the fastest:

def generate_four_pairs(n):
    valids = range(0, n)
    for x00, x01, x02, x03, x10, x11, x12, x13 in itertools.combinations(valids, 8):
      yield [x00, x01, x02, x03], [x10, x11, x12, x13]
      yield [x00, x01, x02, x10], [x03, x11, x12, x13]
      yield [x00, x01, x02, x11], [x03, x10, x12, x13]
      yield [x00, x01, x02, x12], [x03, x10, x11, x13]
      yield [x00, x01, x02, x13], [x03, x10, x11, x12]
      yield [x00, x01, x03, x10], [x02, x11, x12, x13]
      yield [x00, x01, x03, x11], [x02, x10, x12, x13]
      yield [x00, x01, x03, x12], [x02, x10, x11, x13]
      yield [x00, x01, x03, x13], [x02, x10, x11, x12]
      yield [x00, x01, x10, x11], [x02, x03, x12, x13]
      yield [x00, x01, x10, x12], [x02, x03, x11, x13]
      yield [x00, x01, x10, x13], [x02, x03, x11, x12]
      yield [x00, x01, x11, x12], [x02, x03, x10, x13]
      yield [x00, x01, x11, x13], [x02, x03, x10, x12]
      yield [x00, x01, x12, x13], [x02, x03, x10, x11]
      yield [x00, x02, x03, x10], [x01, x11, x12, x13]
      yield [x00, x02, x03, x11], [x01, x10, x12, x13]
      yield [x00, x02, x03, x12], [x01, x10, x11, x13]
      yield [x00, x02, x03, x13], [x01, x10, x11, x12]
      yield [x00, x02, x10, x11], [x01, x03, x12, x13]
      yield [x00, x02, x10, x12], [x01, x03, x11, x13]
      yield [x00, x02, x10, x13], [x01, x03, x11, x12]
      yield [x00, x02, x11, x12], [x01, x03, x10, x13]
      yield [x00, x02, x11, x13], [x01, x03, x10, x12]
      yield [x00, x02, x12, x13], [x01, x03, x10, x11]
      yield [x00, x03, x10, x11], [x01, x02, x12, x13]
      yield [x00, x03, x10, x12], [x01, x02, x11, x13]
      yield [x00, x03, x10, x13], [x01, x02, x11, x12]
      yield [x00, x03, x11, x12], [x01, x02, x10, x13]
      yield [x00, x03, x11, x13], [x01, x02, x10, x12]
      yield [x00, x03, x12, x13], [x01, x02, x10, x11]
      yield [x00, x10, x11, x12], [x01, x02, x03, x13]
      yield [x00, x10, x11, x13], [x01, x02, x03, x12]
      yield [x00, x10, x12, x13], [x01, x02, x03, x11]
      yield [x00, x11, x12, x13], [x01, x02, x03, x10]
      yield [x01, x02, x03, x00], [x10, x11, x12, x13]
      yield [x01, x02, x03, x10], [x00, x11, x12, x13]
      yield [x01, x02, x03, x11], [x00, x10, x12, x13]
      yield [x01, x02, x03, x12], [x00, x10, x11, x13]
      yield [x01, x02, x03, x13], [x00, x10, x11, x12]
      yield [x01, x02, x10, x00], [x03, x11, x12, x13]
      yield [x01, x02, x10, x11], [x00, x03, x12, x13]
      yield [x01, x02, x10, x12], [x00, x03, x11, x13]
      yield [x01, x02, x10, x13], [x00, x03, x11, x12]
      yield [x01, x02, x11, x00], [x03, x10, x12, x13]
      yield [x01, x02, x11, x12], [x00, x03, x10, x13]
      yield [x01, x02, x11, x13], [x00, x03, x10, x12]
      yield [x01, x02, x12, x00], [x03, x10, x11, x13]
      yield [x01, x02, x12, x13], [x00, x03, x10, x11]
      yield [x01, x02, x13, x00], [x03, x10, x11, x12]
      yield [x01, x03, x10, x00], [x02, x11, x12, x13]
      yield [x01, x03, x10, x11], [x00, x02, x12, x13]
      yield [x01, x03, x10, x12], [x00, x02, x11, x13]
      yield [x01, x03, x10, x13], [x00, x02, x11, x12]
      yield [x01, x03, x11, x00], [x02, x10, x12, x13]
      yield [x01, x03, x11, x12], [x00, x02, x10, x13]
      yield [x01, x03, x11, x13], [x00, x02, x10, x12]
      yield [x01, x03, x12, x00], [x02, x10, x11, x13]
      yield [x01, x03, x12, x13], [x00, x02, x10, x11]
      yield [x01, x03, x13, x00], [x02, x10, x11, x12]
      yield [x01, x10, x11, x00], [x02, x03, x12, x13]
      yield [x01, x10, x11, x12], [x00, x02, x03, x13]
      yield [x01, x10, x11, x13], [x00, x02, x03, x12]
      yield [x01, x10, x12, x00], [x02, x03, x11, x13]
      yield [x01, x10, x12, x13], [x00, x02, x03, x11]
      yield [x01, x10, x13, x00], [x02, x03, x11, x12]
      yield [x01, x11, x12, x00], [x02, x03, x10, x13]
      yield [x01, x11, x12, x13], [x00, x02, x03, x10]
      yield [x01, x11, x13, x00], [x02, x03, x10, x12]
      yield [x01, x12, x13, x00], [x02, x03, x10, x11]

For the general approach I would suggest the answer provided by NPE as this is the shortest and easiest readable answer for this problem.

Answer 1

You're doing a lot of unnecessary work by generating all pairs of combinations, and then discarding almost all of them because they contain common elements.

The following addresses this by first taking all subsets of four numbers (in your 2-tuple example), and then splitting each into all possible pairs:

import itertools

def gen_pairs(n, m):
  for both_halves in itertools.combinations(xrange(1, n + 1), 2 * m):
    for first_half in itertools.combinations(both_halves, m):
      second_half = tuple(sorted(set(both_halves) - set(first_half)))
      yield [first_half, second_half]

print sorted(gen_pairs(5, 2))

Note that this does not eliminate duplicates (for example, [(4, 5) (2, 3)] vs [(2, 3), (4, 5)]) and thus produces twice the number of elements you expect.

It is trivial to remove the duplicates, however. This is left as an exercise for the reader.