I have a list of 46 items. Each has a number associated with it. I want to pair these items up in a set of 23 pairs. I want to evaluate a function over each set. How do I generate such a set?
I can use the combinations function from itertools to produce all the 2-ples but I don't see how to generate all the sets of 23 pairs.
How do I do this or is there sample code I can reference?
>>> L=range(46)
>>> def f(x, y): #for example
... return x * y
...
>>> [f(x, y) for x, y in zip(*[iter(L)] * 2)]
[0, 6, 20, 42, 72, 110, 156, 210, 272, 342, 420, 506, 600, 702, 812, 930, 1056, 1190, 1332, 1482, 1640, 1806, 1980]
Edit:
For the powerset of the pairs, we start by creating the pairs the same way. For Python3 use range in place of xrange
S = zip(*[iter(L)] * 2) # set of 23 pairs
[{j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))]
This will be quite a big list, you may want to use a generator expression
for item in ({j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))):
func(item)
First, the natural way to get all the pairs from a list is:
>>> N = 10
>>> input_list = range(N)
>>> [(a,b) for a, b in zip(input_list[::2], input_list[1::2])]
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9)]
If you want to generate all such pairs, I'd do something like (this is what I call Case 1 below):
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = tuple([(a,b) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(pairs)
Granted this as is will differentiate order in pair (e.g., (1,4) is different than (4,1)) as well as consider the order of pairs meaningful. So if you sort the pairs and the set of pairs before adding to the set:
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = sorted([tuple(sorted((a,b))) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(tuple(pairs))
This is not an efficient algorithm (what I call Case 3 below), but for small values of N it will work.
For N=6, using the sorted method.
set([((0, 4), (1, 3), (2, 5)),
((0, 4), (1, 5), (2, 3)),
((0, 1), (2, 3), (4, 5)),
((0, 3), (1, 5), (2, 4)),
((0, 2), (1, 5), (3, 4)),
((0, 4), (1, 2), (3, 5)),
((0, 3), (1, 4), (2, 5)),
((0, 1), (2, 4), (3, 5)),
((0, 5), (1, 4), (2, 3)),
((0, 5), (1, 2), (3, 4)),
((0, 2), (1, 3), (4, 5)),
((0, 3), (1, 2), (4, 5)),
((0, 2), (1, 4), (3, 5)),
((0, 1), (2, 5), (3, 4)),
((0, 5), (1, 3), (2, 4))])
Note the solution space grows exponentially fast; (e.g., for N=6 its 15; N=8 its 105; N=10, its 945, for N=46 will be 25373791335626257947657609375 ~ 2.5 x 1028).
The question asks to break a list of N elements (assuming most general case of all elements being distinct) into a set of (N/2) pairs, and not only do this once, but generate all sets of these pairings. This answer is the only one that does so. Yes, it's exponentially slow, and completely infeasible for N=46. That's why I used N=10.
There are three reasonable interpretations of the problem:
Case 1: Ordering matters both inside a pair in the tuple (e.g., function arguments are not symmetric) and in the order of the pairs in a set of pairs also matters, then we will have N! ways of pairing up the numbers in our answer. Meaning in this case both the pair (0,1) and (1,0) are consider distinct, as well as for the N=4 case we consider the pairings {(0,1), (2,3)} distinct from {(2,3),(0,1)}.
Case 2: Ordering matters in a pair, but order is irrelevant in a set of pairings. This means we consider (0,1) and (1,0) as distinct pairs, but consider (for the N=4 case) that the set {(0,1),(2,3)} is identical to the set {(2,3), (0,1)} and do not need to consider both. In this case we will have N!/(N/2)! pairings, as any given set has (N/2)! different orderings. (I didn't explicitly give this above; but just stop sorting the tuple).
Case 3: Ordering is irrelevant both within a pair and within a set of pairings. This means we consider (0,1) and (1,0) as the same pair (function arguments are symmetric), so we will have N!/( (N/2)! & 2^(N/2) ) sets of pairs (factorial(N)/(factorial(N/2)*2**(N/2))). Each of the (N/2) pairs in each combination will have two internal orderings that contribute.
So depending on how the problem is phrased we should have:
Case 1 | Case 2 | Case 3
----------------------------------------------
N N! | N!/(N/2)! | N!/((N/2)! 2^(N/2))
6 720 | 120 | 15
8 40320 | 1680 | 105
10 3628800 | 30240 | 945
46 5.5x10^57 | 2.1x10^35 | 2x10^28
Note, my algorithm will go through all permutations, and hence will actually run slower for Case 3 (due to sorting) than Case 1, even though a better algorithm for Case 3 could be much faster. However, my answer is still optimal in asymptotic notation as even case 3 is factorial in its asymptotic running time, and completely infeasible to solve for N~46. Granted if you had to do a problem-size at the limit of feasibility (N~16) for Case 3 (e.g., need to generate 518918400.0 pairings), this solution of iterating through all N! permutations, sorting, and throwing out duplicates is sub-optimal.
