所有的不相交的双套 [英] Sets of all disjoint pairs
问题描述
给定一组 {1,2,3,4,5 ... N}
的 N
元素,我们需要找到不相交对所有集合。
Given a set {1,2,3,4,5...n}
of n
elements, we need to find all sets of disjoint pairs.
例如,如果n = 4,输出将是
For example, if n=4, the output would be
{(1,2),(3,4)}, {(1,3),(2,4)}, {(1,4),(2,3)}
我甚至无法弄清楚如何下手。我希望有人可以给我一个建议,关于它的算法使用,可能还有一些执行细节,以及。
I am not even able to figure out how to start. I am hoping someone can give me a suggestion about which algorithm to use, and possibly some implementation details as well.
推荐答案
编辑:
德尔福code递归一代(N-1)!套(1 * 3 * 5 * 7 ... N-1)从n个= 2 * k个元素
Delphi code for recursive generation of (n-1)!! sets (1*3*5*7...n-1) from n=2*k elements
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
添加
变体与奇数长度阵列工作过(奇怪的顺序)
Addition
Variant that works with odd-length array too (weird ordering)
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):
for (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的例子清楚),那么你可以使用的循环赛算法 的
Not relevant now:
If every pair should occur just once (it is not clear from your example with n=4), then you can use round-robin tournament algorithm
这篇关于所有的不相交的双套的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!