在不将它们存储到内存中的情况下一一获得组合的算法

Question

我有一个长度为 N 个整数的数组，我有一个输入整数 X。我需要用总和为 X 的整数组合填充整个数组。我需要找到所有可能的组合，顺序很重要，并且数组具有固定长度 (const N)。例如，如果 X=3 和 N=4 我需要得到这个：

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

此外，我不想将所有可能的组合存储在内存中，但我需要一个一个地获取这些值。例如，当我上次调用 NEXT 方法时，我得到了 [0, 2, 0, 1]。当我再次调用它时，我需要获得下一个组合 [0、1、2、0]。当我再次调用它时，我需要得到 [0, 1, 1, 1] 等等。有没有算法可以做到这一点？谢谢

Answer 1

我已经修改了 colex 顺序中的组合生成以适合您的顺序。
工作 Delphi 代码，我希望它是可以理解的（Dec(P) 等于 P--）

  function next(): Boolean;
  var
    nonzero, last: integer;
  begin
    last := C[n - 1];
    if last = x then  // the last composition
      Exit(False);

    C[n - 1] := 0;
    nonzero := n - 2;
    while C[nonzero] = 0 do //find the last nonzero element
       Dec(nonzero);

    Dec(C[nonzero]);
    C[nonzero + 1] := 1 + last;
    Exit(True);
   end;

begin
  n := 4;
  x := 3;
  SetLength(C, n);
  C[0] := x;
  Memo1.Lines.Add(ArrToStr(C));
  while next() do
    Memo1.Lines.Add(ArrToStr(C));

输出

在不将它们存储到内存中的情况下一一获得组合的算法

Algorithm to get combinations one by one without storing them into memory

java

algorithm

combinatorics