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

Question

I have an array which is N ints long and I have an input int X. I need to populate whole array with combination of ints whose sum gives X. I need to find all possible combinations, the order matters and the array has fixed length (const N). For example if X=3 and N=4 I need to get this:

[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]

Moreover I don't want to store all possible combinations in memory but I need to get these values one by one. For example when I called a method NEXT last time I got [0, 2, 0, 1]. When I call it again I need to get next combination [0, 1, 2, 0]. When I call it again I need to get [0, 1, 1, 1] and so on. Is there an alorithm that can do that? Thank you

To avoid memory issues, you probably want to store a series of chained iterators that only keep what index they have reached so far — information_interchange, May 15 '18 at 15:57
"I have an array[N] of ints" and "all combinations of values in the array". The problem sounds badly formulated. I.e. if you have an array like {0,1,2,3}, the there are 2^4 possible combinations (in the combinatorial sense of the definition) and only the following combinations match e.g. 3 {1,2}, {0,1,2}, {3}, {0,3} — rtybase, May 15 '18 at 17:21
@Vojtech its exactly the same except in your case you don´t want to use more than N numbers, but solutions proposed can be easily modified to add that restriction — juvian, May 15 '18 at 20:46
I updated the description, hope the difference is more clear now. — Vojtech, May 15 '18 at 20:56

score 1 · Accepted Answer · answered May 15 '18 at 16:59

I've modified generation of compositions in colex order to fit your ordering.
Working Delphi code, I hope it is understandable (Dec(P) is equal to 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));

output

Excellent, it so easy and it does exactly what I need. Thank you! — Vojtech, May 15 '18 at 21:20

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

1 Answers1