# combination without repetition of N elements without use for..to..do

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]

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

or for group 3, i wrote:

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

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.

## Answers

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.

**Output**

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