一种生成所有可能的方法来配对数据集中项目的有效方法

Question

这有点像组合问题；我试图找出一种有效的方法来配对数据集中的所有项目。

例如，我有一个长度为 6 的数组：[1,2,3,4,5,6]，我想对数组中的内容进行所有可能的配对：

[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]  
...

等等。在这个例子中，总共有 15 种组合。一般来说，这个解的可能性数应该是（N-1）！！其中 N 是数组的长度或要配对的项目数。在这种情况下，N 将始终为偶数。理想情况下，算法将连续生成所有可能性，而不必存储非常大的数组。

例如，一种方法有点像 'round robin' 调度算法，您将数组拆分为 N/2:

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

顺时针旋转 [5,3,6] 以生成 3 个唯一的配对（垂直计数），[1,2,4] 固定为：

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

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

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

然后顺时针旋转 [4,2,3,6,5] 以生成 5 个唯一的配对，其中 [1] 固定，从最小的最里面的情况 (N=4) 向外直到结束，但递归。事实上，我不确定如何最好地将其表示为代码，或者是否有更有效的方法来执行此操作，因为 N 可能非常大。

Answer 1

您可以使用标准 recursive algorithm for generating permutations of a list 生成对，但有一个扭曲，即每次递归时，您都会沿着列表前进 2 个元素，并且列表中第一个剩余的元素始终是第一个元素您在每次递归时输出的对，第二对是其他每个剩余元素。

总是选择第一个剩余的元素作为对中的第一个项目，避免生成相同的对，但对的顺序不同。

与标准算法一样，您可以就地生成排列，而无需复制数组，方法是就地交换元素，递归，然后再交换回来。

这里有一些 C 代码来演示该算法（我意识到这个问题被标记为 Fortran，但只是将其视为伪代码）。此代码在递归时传递列表和计数，但您可以使用 items 和 itemcount 作为全局变量来实现它：

// 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;
}

输出：

[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]

如果您在大型对象列表上执行此操作，则排列索引列表然后使用它们索引到您的对象数组比对大量数据执行昂贵的交换操作更有效。

Answer 2

哇。现在有来自过去的爆炸。我早在 1993 年就写过这篇文章，并为它提供了 Pascal 源代码。令人惊讶的是，它出现的文章可以在 http://www.drdobbs.com/database/algorithm-alley/184409099#02e5_000d.

在线找到

基本上，我采用了选择排序算法：

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

该方法的问题在于它会生成 {1,2},{1,3},{1,4},{2,3},{2,4}...

事实证明，您可以通过在每次外循环迭代后维护一个交换数组来修改该输出。这是我随文章提供的 Pascal 源代码。

(* ----------------------------------------------------------- *(
**  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.

一种生成所有可能的方法来配对数据集中项目的有效方法

An efficient method to generate all possible ways to pair up items in a data set

algorithm

grouping

combinatorics