Create all unique pairwise permutations

Question

I need to create all possible pairs, but with the restriction that a certain pairing occurs only once in the results. For example:

import itertools for perm in itertools.permutations(range(9)): print zip(perm[::2], perm[1::2]) 

generates all possible two-pair permutations; here is a small subset of the output:

 ... [(8, 4), (7, 6), (5, 3), (0, 2)] [(8, 4), (7, 6), (5, 3), (1, 0)] [(8, 4), (7, 6), (5, 3), (1, 2)] [(8, 4), (7, 6), (5, 3), (2, 0)] [(8, 4), (7, 6), (5, 3), (2, 1)] [(8, 5), (0, 1), (2, 3), (4, 6)] [(8, 5), (0, 1), (2, 3), (4, 7)] [(8, 5), (0, 1), (2, 3), (6, 4)] [(8, 5), (0, 1), (2, 3), (6, 7)] [(8, 5), (0, 1), (2, 3), (7, 4)] [(8, 5), (0, 1), (2, 3), (7, 6)] [(8, 5), (0, 1), (2, 4), (3, 6)] [(8, 5), (0, 1), (2, 4), (3, 7)] [(8, 5), (0, 1), (2, 4), (6, 3)] ... 

How to filter it even more so that I only ever see (8.4) once (in all filtered permutations) and (8.5) only once and (0.1) only once and (4.7) only once, etc.?

Basically, I want permutations so that each two-element pairing happens only once.

I put an additional itertool there to resolve this, but I'm not an expert enough to know what it is.

Update : Gareth Rhys is right - I did not know at all that I was trying to solve the circular motion problem. I have an additional limitation, which is that what I do is grouping people for pair programming exercises. So, if I have an odd number of people, I need to create a group of three to include an odd person for each exercise. My real thinking is to (1) make an even number of people by adding an invisible person. Then, after pairing, find a person paired with an invisible person and randomly place him in an existing group to form a team of three people. However, I wonder if there is still an algorithm or setting for round-robin that does this better.

Update 2 : Theodros solution gives exactly the right result without the inelegant futzing that I talked about above. Everyone was amazingly helpful.

Answer 1

I would like to share another cyclic scheduling implementation using the deque -data structure from the standard library:

 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)) print round_robin(5) [[[0, 4], [1, 3]], [[4, 3], [0, 2]], [[3, 2], [4, 1]], [[2, 1], [3, 0]], [[1, 0], [2, 4]]] print round_robin(2) [[[0, 1]]] 

It puts objects (ints here) in deque. Then he spins and builds successive pairs, taking from both ends in the middle. One can imagine this as folding a deque in the middle back onto itself. To make it clear:

Random uneven items :

  round 1 round 2 # pairs are those numbers that sit ---------- --------- # on top of each other 0 1 2 3 4 8 0 1 2 3 8 7 6 5 7 6 5 4 

In the case of even elements, an additional step is required.
(I skipped the first time because I was only checking the uneven case. This gave a terribly wrong algorithm ... which shows me how important it is to check the edge cases when implementing the algorithm ...)
This special step is that before each turn, I replace the two leftmost elements (which are the first and last element of the deck) - this means that 0 remains all the time in the upper left corner.

Parity Elements:

  round 1 round 2 # pairs are those numbers that sit ---------- --------- # on top of each other 0 1 2 3 0 7 1 2 7 6 5 4 6 5 4 3 

What haunts me in this version is the amount of code duplication, but I could not find a way to improve it, keeping it as readable. Here is my first implementation, which is less readable by IMO:

 def round_robin(n): is_even = (n % 2 == 0) schedule = [] d = deque(range(n)) for i in range(2 * ((n - 1) / 2) + 1): schedule.append( [[d[j], d[-j-1]] for j in range(n/2)]) if is_even: d[0], d[-1] = d[-1], d[0] d.rotate() return schedule 

Update account updated question:

To resolve in an uneven case for groups of three, you just need to change round_robin_odd(d, n) :

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

This gives:

 print round_robin(5) [[[0, 4], [1, 3, 2]], [[4, 3], [0, 2, 1]], [[3, 2], [4, 1, 0]], [[2, 1], [3, 0, 4]], [[1, 0], [2, 4, 3]]] 

Answer 2

Pass the set list to make sure that each tuple exists only once.

 >>> from itertools import permutations >>> set( [ zip( perm[::2], perm[1::2] ) for perm in permutations( range( 9 ) ) ] ) set([(7, 3), (4, 7), (1, 3), (4, 8), (5, 6), (2, 8), (8, 0), (3, 2), (2, 1), (6, 2), (1, 6), (5, 1), (3, 7), (2, 5), (8, 5), (0, 3), (5, 8), (4, 0), (1, 2), (3, 8), (3, 1), (6, 7), (2, 0), (8, 1), (7, 6), (3, 0), (6, 3), (1, 5), (7, 2), (3, 6), (0, 4), (8, 6), (3, 5), (4, 1), (6, 4), (5, 4), (2, 6), (8, 2), (2, 7), (7, 1), (4, 5), (8, 3), (1, 4), (6, 0), (7, 5), (2, 3), (0, 7), (8, 7), (4, 2), (1, 0), (0, 8), (6, 5), (4, 6), (0, 1), (5, 3), (7, 0), (6, 8), (3, 4), (6, 1), (5, 7), (5, 2), (0, 2), (7, 4), (0, 6), (1, 8), (4, 3), (1, 7), (0, 5), (5, 0), (7, 8), (2, 4), (8, 4)]) 

From your description, you want each of the two-line permutations of range( 9 ) above to give you all the different permutations based on your code. But it is rather inefficient.

However, you can simplify your code even further by following these steps:

 >>> list( permutations( range( 9 ), 2 ) ) [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (4, 8), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7)] 

The permutations method also takes a length argument, which allows you to specify the length of the returned tuple. So, you used the correct itertool function, but missed the tuple length parameter.

documentation itertools.permutations

Answer 3

As MatthieuW says in this answer , it looks like you are trying to create a schedule for a round robin tournament . This can be easily generated using this algorithm , the main difficulty is processing an odd number of teams (when each team gets a date in one round).

 def round_robin_schedule(n): """ Generate a round-robin tournament schedule for `n` teams. """ m = n + n % 2 # Round up to even number. for r in xrange(m - 1): def pairing(): if r < n - 1: yield r, n - 1 for i in xrange(m // 2 - 1): p, q = (r + i + 1) % (m - 1), (m + r - i - 2) % (m - 1) if p < n - 1 and q < n - 1: yield p, q yield list(pairing()) 

For example, with nine commands:

 >>> list(round_robin_schedule(9)) [[(0, 8), (2, 7), (3, 6), (4, 5)], [(1, 8), (2, 0), (4, 7), (5, 6)], [(2, 8), (3, 1), (4, 0), (6, 7)], [(3, 8), (4, 2), (5, 1), (6, 0)], [(4, 8), (5, 3), (6, 2), (7, 1)], [(5, 8), (6, 4), (7, 3), (0, 1)], [(6, 8), (7, 5), (0, 3), (1, 2)], [(7, 8), (0, 5), (1, 4), (2, 3)], [(0, 7), (1, 6), (2, 5), (3, 4)]]