所有不相交对的集合

Question

给定一组 {1,2,3,4,5...n} 个 n 个元素，我们需要找到所有不相交的对组。

例如，如果 n=4，则输出为

{(1,2),(3,4)},   {(1,3),(2,4)},   {(1,4),(2,3)}

我什至不知道如何开始。我希望有人可以给我一个关于使用哪种算法的建议，以及可能的一些实现细节。

Answer 1

你必须看到这里的模式。

对于{1, 2, 3, 4}。

取第一个元素与右边的所有元素配对

(1, 2), (1, 3), (1, 4)

取第二个元素与右边的所有元素配对

(2, 3), (2, 4)

取第三个元素与右边所有元素配对

(3, 4)

...等等

Notice the pattern here.

您需要一个外部循环来遍历元素并 select 每个元素一个一个地迭代。

还有另一个内部循环，用于遍历 selected 元素右侧的元素，并与每个元素配对。

Answer 2

编辑：
Delphi 递归生成 (n-1) 的代码！！从 n=2*k 个元素中设置 (1*3*5*7...n-1)

var
  A: TArray<Integer>;

  procedure Swap(i, j: integer);
  var
    t : integer;
  begin
    t := A[i];
    A[i] := A[j];
    A[j] := t;
  end;

  procedure MakePairs(Start: Integer; Pairs: string);
  var
    i: Integer;
  begin
    if Start >= Length(A) then
      Writeln(Pairs)
    else
    for i := Start + 1 to High(A) do begin
      Swap(Start + 1, i); //store used element in the array beginning
      MakePairs(Start + 2, Pairs + Format('(%d,%d)', [A[Start], A[Start + 1]]));
      Swap(Start + 1, i); //get it back
    end;
  end;

begin
  A := TArray<Integer>.Create(1,2,3,4,5,6);
  //be sure that array length is even!!!
  MakePairs(0, '');
  Writeln(PairCount);

输出：

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

加法
也适用于奇数长度数组的变体（奇怪的顺序）

  procedure MakePairs(Start: Integer; Pairs: string);
  var
    i: Integer;
    OddFlag: Integer;
  begin
    if Start >= Length(A) then
      Memo1.Lines.Add(Pairs)
    else begin
      Oddflag := (High(A) - Start) and 1;
      for i := Start + OddFlag to High(A) do begin
        Swap(Start + OddFlag, i);
        if OddFlag = 1 then
          MakePairs(Start + 2, Pairs + Format('(%d,%d)', [A[Start], A[Start + 1]]))
        else
          MakePairs(Start + 1, Pairs);
        Swap(Start + OddFlag, i);
      end;
    end;
  end;

对于 (1,2,3,4,5)：

(2,3)(4,5)
(2,4)(3,5)
(2,5)(4,3)
(1,3)(4,5)
(1,4)(3,5)
(1,5)(4,3)
(2,1)(4,5)
(2,4)(1,5)
(2,5)(4,1)
(2,3)(1,5)
(2,1)(3,5)
(2,5)(1,3)
(2,3)(4,1)
(2,4)(3,1)
(2,1)(4,3)
15

现在不相关：
如果每对只出现一次（从你的例子中 n=4 不清楚），那么你可以使用 round-robin tournament algorithm

n=4 case example here

所有不相交对的集合

Sets of all disjoint pairs

c

algorithm

permutation

set