algorithm - 不重复 N 个元素的组合，不使用 for..to..do

Question

我想在列表中加载 N 个数字的组合而不重复，以输入元素和组。 例如，对于 4 个元素 [1,2,3,4]，我有:

Group 1: [1][2][3][4]; 
Group 2: [1,2][1,3][1,4][2,3][2,4][3,4];
Group 3: [1,2,3][1,2,4][1,3,4][2,3,4]
Group 4: [1,2,3,4]

现在，我已经使用嵌套循环解决了它，例如对于第 2 组，我写:

  for x1 := 1 to 3 do
    for x2 := Succ(x1) to 4 do
      begin
        // x1, x2 // 
      end

或者对于第 3 组，我写道:

  for x1 := 1 to 2 do
    for x2 := Succ(x1) to 3 do
      for x3 := Succ(x2) to 4 do
      begin
        // x1, x2, x3 // 
      end

其他群体也是如此。 一般来说，如果我想为 N 组做这件事，就像我能做的那样，而不用写 N 个带有嵌套循环的过程？ 我想过两次 while..do 循环，一个用于计数器，一个用于组计数，但这有点难，我想知道是否有一些更简单、更快速的解决方案，也可以使用运算符 bool 值或类似的东西. 谁能给我一些建议？非常感谢。

Answer 1

看来您正在寻找一种计算所有 k 组合的快速算法。以下 Delphi 代码是对此处找到的 C 代码的直接翻译:Generating Combinations .我什至修复了该代码中的错误!

program kCombinations;

{$APPTYPE CONSOLE}

// Prints out a combination like {1, 2}
procedure printc(const comb: array of Integer; k: Integer);
var
  i: Integer;
begin
    Write('{');
    for i := 0 to k-1 do
  begin
    Write(comb[i]+1);
    if i<k-1 then
      Write(',');
  end;
    Writeln('}');
end;

(*
Generates the next combination of n elements as k after comb
  comb => the previous combination ( use (0, 1, 2, ..., k) for first)
  k => the size of the subsets to generate
  n => the size of the original set

  Returns: True if a valid combination was found, False otherwise
*)
function next_comb(var comb: array of Integer; k, n: Integer): Boolean;
var
  i: Integer;
begin
    i := k - 1;
    inc(comb[i]);
    while (i>0) and (comb[i]>=n-k+1+i) do
  begin
    dec(i);
        inc(comb[i]);
    end;

    if comb[0]>n-k then// Combination (n-k, n-k+1, ..., n) reached
  begin
    // No more combinations can be generated
    Result := False;
    exit;
  end;

    // comb now looks like (..., x, n, n, n, ..., n).
    // Turn it into (..., x, x + 1, x + 2, ...)
    for i := i+1 to k-1 do
        comb[i] := comb[i-1]+1;

  Result := True;
end;

procedure Main;
const
    n = 4;// The size of the set; for {1, 2, 3, 4} it's 4
    k = 2;// The size of the subsets; for {1, 2}, {1, 3}, ... it's 2
var
  i: Integer;
  comb: array of Integer;
begin
  SetLength(comb, k);// comb[i] is the index of the i-th element in the combination

    //Setup comb for the initial combination
  for i := 0 to k-1 do
        comb[i] := i;

    // Print the first combination
    printc(comb, k);

    // Generate and print all the other combinations
    while next_comb(comb, k, n) do
        printc(comb, k);
end;

begin
  Main;
  Readln;
end.

输出

{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}