Python: Generating All Pairwise-Unique Pairings

Question

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.

Answer 1

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

Answer 2

In the linked question "Generating all unique pair permutations", (here), an algorithm is given to generate a round-robin schedule for any given n. That is, each possible set of matchups/pairings for n teams.

So for n = 4 (assuming exclusive), that would be:

[0, 3], [1, 2]
[0, 2], [3, 1]
[0, 1], [2, 3]

Now we've got each of these partitions, we just need to find their permutations in order to get the full list of pairings. i.e [0, 3], [1, 2] is a member of a group of four: [0, 3], [1, 2] (itself) and [3, 0], [1, 2] and [0, 3], [2, 1] and [3, 0], [2, 1].

To get all the members of a group from one member, you take the permutation where each pair can be either flipped or not flipped (if they were, for example, n-tuples instead of pairs, then there would be n! options for each one). So because you have two pairs and options, each partition yields 2 ^ 2 pairings. So you have 12 altogether.

Code to do this, where round_robin(n) returns a list of lists of pairs. So round_robin(4) --> [[[0, 3], [1, 2]], [[0, 2], [3, 1]], [[0, 1], [2, 3]]].

def pairs(n):
    for elem in round_robin(n):
        for first in [elem[0], elem[0][::-1]]:
            for second in [elem[1], elem[1][::-1]]:
                print (first, second)

This method generates less than you want and then goes up instead of generating more than you want and getting rid of a bunch, so it should be more efficient. ([::-1] is voodoo for reversing a list immutably).

And here's the round-robin algorithm from the other posting (written by Theodros Zelleke)

from collections import deque

def round_robin_even(d, n):
    for i in range(n - 1):
        yield [[d[j], d[-j-1]] for j in range(n/2)]
        d[0], d[-1] = d[-1], d[0]
        d.rotate()

def round_robin_odd(d, n):
    for i in range(n):
        yield [[d[j], d[-j-1]] for j in range(n/2)]
        d.rotate()

def round_robin(n):
    d = deque(range(n))
    if n % 2 == 0:
        return list(round_robin_even(d, n))
    else:
        return list(round_robin_odd(d, n))