所有不相交的对的集合
给定{1,2,3,4,5...n} n元素的{1,2,3,4,5...n}组，我们需要找到所有不相交的对。
例如，如果n = 4，则输出为
{(1,2),(3,4)}, {(1,3),(2,4)}, {(1,4),(2,3)}
我甚至无法弄清楚如何开始。 我希望有人可以给我一个关于使用哪种算法的建议，以及可能的一些实现细节。
编辑：
用于递归生成（n-1）的Delphi代码!! 从n = 2 * k个元素设置（1 * 3 * 5 * 7 … n-1）
var A: TArray; 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 .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的例子中不清楚），那么你可以使用循环赛锦标赛算法
这里n = 4个案例
你必须在这里看到模式。
对于{1, 2, 3, 4} 。
取第一个元素并与右边的所有元素成对。
(1, 2), (1, 3), (1, 4)
取第二个元素并与右侧的所有元素成对。
(2, 3), (2, 4)
取第三个元素并与右边的所有元素成对。
(3, 4)
…等等
注意这里的模式。
您需要一个外部循环来迭代元素并逐个选择每个元素。
另一个内循环遍历所选元素右侧的元素，并与它们中的每一个元素成对。