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.
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}