I am looking for a Pythonic method to generate all pairwise-unique unique pairings (where a pairing is a system consisting of pairs, and pairwise-unique indicates that (a,b) ≠ (b,a)) for a set containing even number n items.
I like the code from here:
for perm in itertools.permutations(range(n)):
print zip(perm[::2], perm[1::2])
except that it generates all order-unique, pairwise-unique pairings, or (n/2)! times more pairings than I want (redundancy), which, although I can filter out, really bog down my program at large n.
That is, for n = 4, I am looking for the following output (12 unique pairings):
[(0, 1), (2, 3)]
[(0, 1), (3, 2)]
[(1, 0), (2, 3)]
[(1, 0), (3, 2)]
[(1, 2), (0, 3)]
[(1, 2), (3, 0)]
[(1, 3), (0, 2)]
[(2, 0), (1, 3)]
[(2, 0), (3, 1)]
[(3, 1), (0, 2)]
[(0, 3), (2, 1)]
[(3, 0), (2, 1)]
Note that (a,b) ≠ (b,a).
Is this possible? I am also okay with a function that generates the 3 non–pairwise-unique pairings for n = 4 where (a,b) = (b,a), as it is straightforward to permute what I need from there. My main goal is to avoid the superfluous permutations on the order of the pairs in the pairing.
Thanks in advance for your help and suggestions—I really appreciate it.
I think this gives you the fundamental pairings that you need: 1 when N=2; 3 when N=4; 15 when N=6; 105 when n=8, etc.
import sys
def pairings(remainder, partial = None):
partial = partial or []
if len(remainder) == 0:
yield partial
else:
for i in xrange(1, len(remainder)):
pair = [[remainder[0], remainder[i]]]
r1 = remainder[1:i]
r2 = remainder[i+1:]
for p in pairings(r1 + r2, partial + pair):
yield p
def main():
n = int(sys.argv[1])
items = list(range(n))
for p in pairings(items):
print p
main()