An efficient method to generate all possible ways

Question

This is somewhat of a combinatorial problem; I'm trying to figure out an efficient way to pair up all items in a data set.

For example, I have an array of length 6: [1,2,3,4,5,6], and I want to make all possible pairings of the contents in the array as so:

[1,2],[3,4],[5,6]  
[1,2],[3,5],[4,6]  
[1,2],[3,6],[4,5]  
[1,3],[2,4],[5,6]  
[1,3],[2,5],[4,6]  
...

and so on. In this example, there would be 15 combinations total. In general, the number of possibilities in this solution should be (N-1)!! where N is the length of the array or the number of items to be paired up. N will always be even in this case. Ideally, an algorithm will generate all possibilities serially, without having to store very large arrays.

For example, one way would work somewhat like a 'round robin' scheduling algorithm where you split the array into N/2:

[1,2,3]  
[4,5,6]  

and rotate the [5,3,6] clockwise to generate 3 unique pairings (counting vertically) with [1,2,4] fixed as so:

[1,2,3]  
[4,5,6]

[1,2,5]  
[4,6,3]  

[1,2,6]  
[4,3,5]

and then rotate [4,2,3,6,5] clockwise to generate 5 unique pairings with [1] fixed, going from the smallest innermost case (N=4) outwards until the end, but recursively. As it is I'm not sure how to best express this as code or if there is a more efficient way of doing this, as N can be very large.

Answer 1

Wow. Now there's a blast from the past. I wrote about this back in 1993 and provided Pascal source code for it. Surprisingly, the article in which it appeared is available online at http://www.drdobbs.com/database/algorithm-alley/184409099#02e5_000d.

Basically, I adapted a selection sort algorithm:

for x = 0 to n-2
    for y = x+1 to n-1
        write x, y

The problem with that approach is that it generates {1,2},{1,3},{1,4},{2,3},{2,4}...

It turns out that you can modify that output by maintaining a swap array that you manipulate after every iteration of the outer loop. Here's the Pascal source code that I supplied with the article.

(* ----------------------------------------------------------- *(
**  pairings.pas -- Select sports-event team pairings          **
** ------------------------------------------------------------**
**   This program generates team pairings for sports events.   **
**   Each team is guaranteed to play each other team exactly   **
**   once. No team will play more than one game per day.       **
**   An asterisk ('*') means a day off for that team.          **
**   For example, 5 teams produces this output:                **
**     Day 1 - 12 34 5*                                        **
**     Day 2 - 13 25 4*                                        **
**     Day 3 - 14 2* 35                                        **
**     Day 4 - 15 3* 24                                        **
**     Day 5 - 1* 45 23                                        **
** ------------------------------------------------------------**
**   Copyright (c) 1993 by Jim Mischel. All rights reserved.   **
)* ----------------------------------------------------------- *)

program pairings;
const
  TEAMCOUNT = 5;
var
  TeamNames: Array [1 .. TEAMCOUNT + 1] of Char;
  SwapArray: Array [1 .. TEAMCOUNT + 1] of Integer;
  x, Temp, Day: Integer;
  TempChar: Char;
const
  NTeams: Integer = TEAMCOUNT;
begin
{ Set up team names. Normally read from a file. }
  for x := 1 to NTeams do
    TeamNames[x] := Chr(x + Ord('0'));
  if Odd(NTeams) then
  begin
    NTeams := NTeams + 1;
    TeamNames[NTeams] := '*'
  end;
{ Set up the array that controls swapping. }
  for x := 1 to NTeams do
    SwapArray[x] := x;
  for Day := 1 to NTeams - 1 do
  begin
    Write('Day ', Day, ' -');
{ Write the team pairings for this day }
    x := 1;
    while x < NTeams do
    begin
      Write(' ', TeamNames[x], TeamNames[x + 1]);
      x := x + 2;
    end;
    WriteLn;
{ Perform swaps to prepare array for next day's pairings. }
    if Odd(Day)
      then x := 2
      else x := 3;
    while x < NTeams do
    begin
      TempChar := TeamNames[SwapArray[x]];
      TeamNames[SwapArray[x]] := TeamNames[SwapArray[x + 1]];
      TeamNames[SwapArray[x + 1]] := TempChar;
      Temp := SwapArray[x];
      SwapArray[x] := SwapArray[x + 1];
      SwapArray[x + 1] := Temp;
      x := x + 2
    end
  end
end.

Answer 2

You can generate the pairs using the standard recursive algorithm for generating permutations of a list, but with a twist that each time you recurse you advance 2 elements along the list, and the first remaining element in the list is always the first element of the pair you output at each recursion, with the second of the pair being each of the other remaining elements.

Always choosing the first remaining element as the first item in the pair avoids generating the same pairings with the pairs in different order.

As with the standard algorithm, you can generate the permutations in place without making copies of the array, by swapping elements in place, recursing and then swapping back.

Here is some C code to demonstrate the algorithm (I realise this question is tagged Fortran but just think of it as pseudo code). This code passes the list and count when it recurses, but you could implement it with items and itemcount as global variables:

// start is the current position in the list, advancing by 2 each time
// pass 0 as start when calling at the top level
void generatePairings(int* items, int itemcount, int start)
{
    if(itemcount & 1)
        return; // must be an even number of items

    // is this a complete pairing?
    if(start == itemcount)
    {
        // output pairings:
        int i;
        for(i = 0; i<itemcount; i+=2)
        {
            printf("[%d, %d] ", items[i], items[i+1]);
        }
        printf("\n");
        return;
    }

    // for the next pair, choose the first element in the list for the
    // first item in the pair (meaning we don't have to do anything 
    // but leave it in place), and each of the remaining elements for
    // the second item:
    int j;
    for(j = start+1; j<itemcount; j++)
    {
        // swap start+1 and j:
        int temp = items[start+1];
        items[start+1] = items[j];
        items[j] = temp;

        // recurse:
        generatePairings(items, itemcount, start+2);

        // swap them back:
        temp = items[start+1];
        items[start+1] = items[j];
        items[j] = temp;
    }
}

int main(void) {
    int items[6] = {1, 2, 3, 4, 5, 6};
    generatePairings(items, 6, 0);

    return 0;
}

Output:

[1, 2] [3, 4] [5, 6] 
[1, 2] [3, 5] [4, 6] 
[1, 2] [3, 6] [5, 4] 
[1, 3] [2, 4] [5, 6] 
[1, 3] [2, 5] [4, 6] 
[1, 3] [2, 6] [5, 4] 
[1, 4] [3, 2] [5, 6] 
[1, 4] [3, 5] [2, 6] 
[1, 4] [3, 6] [5, 2] 
[1, 5] [3, 4] [2, 6] 
[1, 5] [3, 2] [4, 6] 
[1, 5] [3, 6] [2, 4] 
[1, 6] [3, 4] [5, 2] 
[1, 6] [3, 5] [4, 2] 
[1, 6] [3, 2] [5, 4] 

If you are doing this on a list of large objects, it's more efficient to permute a list of indices and then use those to index into your array of objects, rather than doing expensive swap operations on large amounts of data.