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

Question

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.

Solution 1

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}

Solution 2

This seems to be a question that comes up over and over and a few bits of code are kicking about that address the problem. A very nice algorithm in some code has been written but it wasn't strictly clean C and not portable across UNIX or Linux or any POSIX system, therefore I cleaned it up and added warning messages, usage and the ability to provide a set size and sub_set size on the command line. Also comb[] has been transitioned to a more general pointer to an array of integers and calloc used to zero out the memory needed for whatever set size one may want.

The following is ISO IEC 9899:1999 C clean :

/*********************************************************************
 * The Open Group Base Specifications Issue 6
 * IEEE Std 1003.1, 2004 Edition
 *
 *    An XSI-conforming application should ensure that the feature 
 *    test macro _XOPEN_SOURCE is defined with the value 600 before 
 *    inclusion of any header. This is needed to enable the 
 *    functionality described in The _POSIX_C_SOURCE Feature Test 
 *    Macro and in addition to enable the XSI extension.
 *
 * Compile with c99 or with gcc and CFLAGS to include options 
 * -std=iso9899:199409 -pedantic-errors in order to ensure compliance
 * with ISO IEC 9899:1999 C spec. 
 *
 * Code cleanup and transition to comb as a pointer to type ( int * ) 
 * array by Dennis Clarke [email protected]  28 Dec 2012 
 *
 *********************************************************************/
#define _XOPEN_SOURCE 600

#include <stdio.h>
#include <stdlib.h>

/* Prints out a combination like {1, 2} */
void printc( int *comb, int k) {

    int j;
    printf("{ ");

    for ( j = 0; j < k; ++j )
        printf("%d , ", *( comb + j ) + 1 );

    printf( "\b\b}\n" );

} /* printc */

/**********************************************************************
    next_comb(int comb[], int k, int n)
    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: 1 if a valid combination was found
    0, otherwise
**********************************************************************/

int next_comb( int *comb, int k, int n) {

    int i = k - 1;
    ++*( comb + i );
    while ( ( i >= 0 ) && ( *( comb + i ) >= n - k + 1 + i ) ) {
        --i;
        ++*( comb + i );
    }

    if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
        return 0; /* No more combinations can be generated */

    /* comb now looks like (..., x, n, n, n, ..., n).
     * Turn it into (..., x, x + 1, x + 2, ...) */
    for (i = i + 1; i < k; ++i)
        *( comb + i ) = *( comb + ( i - 1 ) ) + 1;

    return 1;

} /* next_comb */

int main(int argc, char *argv[]) {

    int *comb, i, n, k;

    n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */
    k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */

    if ( argc < 3 ) { 
        printf ( "\nUSAGE : %s n k\n", argv[0] );
        printf ( "      : Where n is the set size and k the sub set size.\n" );
        printf ( "      : Note that k <= n\n" );
        return ( EXIT_FAILURE );
    }

    n = atoi ( argv[1] );
    k = atoi ( argv[2] );

    if ( k > n ) {
        printf ( "\nWARN  : k > n is not allowed.\n" );
        printf ( "USAGE : %s n k\n", argv[0] );
        printf ( "      : Where n is the set size and k the sub set size.\n" );
        printf ( "      : Note that k <= n\n" );
        return ( EXIT_FAILURE );
    }

    comb = ( int * ) calloc( (size_t) k, sizeof(int) );

    for ( i = 0; i < k; ++i)
        *( comb + i ) = i;

    /* Print the first combination */
    printc( comb, k );

    /* Generate and print all the other combinations */
    while ( next_comb( comb, k, n ) )
        printc( comb, k );

    free ( comb );

    return ( EXIT_SUCCESS );

}

One may compile the above on an Opteron based machine thus :

$ echo $CFLAGS 
-m64 -g -malign-double -std=iso9899:199409 -pedantic-errors -mno-mmx 
-mno-sse -fexceptions -fpic -fvisibility=default -mtune=opteron 
-march=opteron -m128bit-long-double -mpc80 -Wl,-q
$ gcc $CFLAGS -o combinations combinations.c 

A quick trivial test with a set size of 10 and a sub-set of 6 will be thus :

$ ./combinations 10 6 | wc -l 
210

The math is correct :

 ( 10 ! ) / ( ( 10 - 6 )!  *  ( 6! ) )  =   210 unique combinations. 

Now that the integer array comb is based on a pointer system we are only restricted by available memory and time. Therefore we have the following :

$ /usr/bin/time -p ./combinations 20 6 | wc -l 
real 0.11
user 0.10
sys 0.00
38760

This looks correct :

( 20 ! ) / ( ( 20 - 6 )!  *  ( 6! ) )  = 38,760 unique combinations

We may now push the limits a bit thus :

$ ./combinations 30 24 | wc -l 
593775

Again the math agrees with the result :

( 30 ! ) / ( ( 30 - 24 )!  *  ( 24! ) )  =  593 775 unique combinations

Feel free to push the limits of your system :

$ /usr/bin/time -p ./combinations 30 22 | wc -l  
real 18.62
user 17.76
sys 0.83
5852925

I have yet to try anything larger but the math looks correct as well as the output thus far. Feel free to let me know if some correction is needed.

Dennis Clarke [email protected] 28 Dec 2012

Solution 3

Here's a rather fun solution reliant on bitsets. As it stands it's limited to sets of size not greater than 32. I don't think that's a practical limitation since there are a lot of subsets for a set of cardinality greater than 32.

The output is not in the order that you want, but that would be easy enough to remedy if it matters to you.

program VisitAllSubsetsDemo;

{$APPTYPE CONSOLE}

procedure PrintBitset(Bitset: Cardinal; Size: Integer);
var
  i: Integer;
  Mask: Cardinal;
  SepNeeded: Boolean;
begin
  SepNeeded := False;
  Write('{');
  for i := 1 to Size do begin
    Mask := 1 shl (i-1);
    if Bitset and Mask<>0 then begin
      if SepNeeded then begin
        Write(',');
      end;
      Write(i);
      SepNeeded := True;
    end;
  end;
  Writeln('}');
end;

procedure EnumerateSubsets(Size: Integer);
var
  Bitset: Cardinal;
begin
  for Bitset := 0 to (1 shl Size)-1 do begin
    PrintBitset(Bitset, Size);
  end;
end;

begin
  EnumerateSubsets(4);
end.

Output

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

And here is a variant that just lists the subsets of a specified cardinality:

function SetBitCount(Bitset: Cardinal; Size: Integer): Integer;
var
  i: Integer;
  Mask: Cardinal;
begin
  Result := 0;
  for i := 1 to Size do begin
    Mask := 1 shl (i-1);
    if Bitset and Mask<>0 then begin
      inc(Result);
    end;
  end;
end;

procedure EnumerateSubsets(Size, NumberOfSetBits: Integer);
var
  Bitset: Cardinal;
begin
  for Bitset := 0 to (1 shl Size)-1 do begin
    if SetBitCount(Bitset, Size)=NumberOfSetBits then begin
      PrintBitset(Bitset, Size);
    end;
  end;
end;

begin
  EnumerateSubsets(4, 2);
end.

Output

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

Solution 4

Following the link that David posted and clicking around led me to an article where they coin the term "Banker's Search", which seems to fit your pattern.

The article provides an example solution in C++, utilizing recursion:

Efficiently Enumerating the Subsets of a Set

View more solutions

Comments

[David Heffernan]

recursion is good solution to the problem, but this code is in the wrong language

[syang]

lol, excuse me for not knowing the desired language. it looks like delphi, but I'd rather write in generic C to make sure it's right code.

[Marcello Impastato]

Very good, but for display only set of N element with group M? For example, with group = 2, display only: {1,2}{1,3}{1,4}{2,3}{2,4}{3,4} as i can adjust it? Thanks very much.

[Marcello Impastato]

Thanks very much, it solve mine problem. Thanks again. There is only a bit problem, until to 20 elements it is ok, much fast, but with 25 o more elements into set it is every more slowly :( is possible solve this? Looking code, not understand what take much time. Thanks again.

[David Heffernan]

Well, if you want all subsets it's hard to go much faster than the basic loop here. There just are an immense number of subsets. If you only want subsets for a certain cardinality then it becomes more tractable. Let me think about that.

[David Heffernan]

@Marcello Try my other answer. I think it is exactly what you want!

[Marcello Impastato]

Thanks, this solution is more fast. Very very good, thanks again :)

[David Heffernan]

It evens outputs in the order you are expecting. Nice algorithm.

[Ken White]

This question is tagged delphi, and there's no mention of c whatsoever in this question. Your answer is like posting "Si, señor" when someone asks "How do you say 'Yes, sir' in Chinese?". :-) (And we don't use signatures in questions or answers here; you have a user profile where you can include things like your email address if you want to do so, but don't do it in your posts. The FAQ mentions this, in case you're not sure. Questions and answers are also automatically dated and time stamped, so you don't need to add those either.)