Generate all pairs of 4 elements from n elements

Question

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

As an example that helps to understand the problem, I use a smaller version of the problem, pairs of 2-tuples given by an array of size 5 . The expected result for pairs of 2-tuples would lead to 15 points (tuples are ordered, no duplicates):

[(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 to do this is to use itertools from python and go through all the elements returned by itertools.combinations , do 2 itertools.combinations and find 2 pairs that don't share one 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 does its job, but is inefficient due to two cycles and works only for small n in a given period of time. Could this be more effective?

---

Update: after some answers I appreciated the suggestions. The best for my particular case is the (advanced) algorithm provided by the (now deleted) MSeifert response, 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 a 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 do 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 are this, first taking all the subsets of four numbers (in the example with two tuples), and then breaking them 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 therefore doubles the number of expected elements.

However, it is trivial to remove duplicates. This remains as an exercise for the reader.

Answer 2

You can use permutations and splitting, which can be faster:

 array = ... size = 4 c = itertools.permutations(array) for t in c: a = [] for i in range(0, len(t), size): if i + size <= len(t): a.append(t[i:i+size]) yield a 

Note. In the case where the length of the array is not a multiple of the size, this solution works, but produces duplicates.

Answer 3

I would do:

 from itertools import combinations sample = range(1,6) x1 = [subset for subset in combinations(sample,2)] #getting the set of tuples x2 = [list(subset) for subset in combinations(x1,2)] #getting the pair of tuples x3 = [x for x in x2 if (set(x[0]) & set(x[1]) == set())] #finally filtering the tuples with no intersection 

Output:

 [[(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)]] 

Answer 4

And here is the code for generating the MSeifert output statements :) (And this only gives 35 of them, which means there are no duplicates :)

 def g(L, n, k, A, B): if len(A) == k: return [[tuple(A), tuple([L[i] for i in xrange(0, n + 1)] + B)]] elif len(B) == k: return [[tuple([L[i] for i in xrange(0, n + 1)] + A), tuple(B)]] return g(L, n - 1, k, A, [L[n]] + B[0:]) + g(L, n - 1, k, [L[n]] + A[0:], B) def f(L): assert(len(L) > 3 and len(L) % 2 == 0) return g(L, len(L) - 2, len(L) / 2, [], [L[-1]]) for i in f(['x00','x01','x02','x03','x10','x11','x12','x13']): print(i)