组合而不重复N元素，而不用于... to..do [英] combination without repetition of N elements without use for..to..do

问题描述

我想在列表中加载N个号码而不重复，给出输入元素和组。
例如，有4个元素[1,2,3,4]，我有：

i want load in a list the combination of N number without repetition, giving to input the elements and group. For example, with 4 elements [1,2,3,4], i have for:

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，我写：

Now, i have solved it using nested loop for, for example with group 2, i write:

  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嵌套循环的程序？
我已经想到了一个double while..do循环一个用于计数器，一个用于组数，但是很难，我想知道如果有一些解决方案更简单和快速，也使用运算符布尔或某事如此。
谁能给我一些建议呢？非常感谢。

and so for other groups. In general, if i want to do it for group N, as i can to do, without write N procedures with nested loops? I have thinked to a double while..do loop one to use for counter and one to use for groups count, but so is little hard, i wanted know if there was some solution more simple and fast, too using operator boolean or something so. Who can give me some suggest about it? Thanks very much.

推荐答案

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

It seems you are looking for a fast algorithm to calculate all k-combinations. The following Delphi code is a direct translation of the C code found here: Generating Combinations. I even fixed a bug in that code!

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}

这篇关于组合而不重复N元素，而不用于... to..do的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！