Sets of all disjoint pairs

问题:

Given a set {1,2,3,4,5...n} of n elements, we need to find all sets of disjoint pairs.

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.

回答1:

Edit:
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);

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)
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;

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

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

n=4 case example here

回答2:

You have to see the pattern here.

For {1, 2, 3, 4}.

Take the first element and make pairs with all the elements on the right.

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

Take the second element and make pairs with all the elements on the right.

(2, 3), (2, 4)

Take the third element and make pairs with all the elements on the right.

(3, 4)

...and so on

Notice the pattern here.

---

You would need an outer loop to iterate over the elements and select each element one by one.

And another inner loop to iterate over the elements on the right of the selected element and make a pair with each one of them.