组合，不重复N个元素，无需使用..to..do

一尘不染

组合，不重复N个元素，无需使用..to..do

algorithm

我想将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个过程，可以吗？我曾想过一会儿..do循环一个用于计数器，一个用于组计数，但是这有点困难，我想知道是否有一些更简单，更快速的解决方案，也可以使用运算符boolean或类似的东西。谁能给我一些建议？非常感谢。

阅读 315

2020-07-28

共1个答案

一尘不染

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

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}

2020-07-28