combination without repetition of N elements witho

问题:

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.

回答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}

回答2:

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}

回答3:

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 [e-mail]  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 [e-mail] 28 Dec 2012

回答4:

Unless you can't make function calls by some requirement, do this:

select_n_from_list(int *selected, int n, int *list, int list_size):
    if (n==0) {
        // print all numbers from selected by traversing backward
        // you can set the head to a special value or make the head location
        // a static variable for lookup
    }

    for (int i=0; i<=list_size-n; i++) {
        *selected = list[i];
        select_n_from_list(selected+1, n-1, list+i+1, list_size-i-1);
    }
}

You really need some sort of recursion because you need automatic storage for intermediate results. Let me know if there's special requirement that makes this solution don't work.

回答5:

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

回答6:

I created this script here and worked very well:

$(document).ready(function(){
    $("#search").on('click', function(){
        var value = $("#fieldArray").val().split(",");
        var results = new SearchCombinations(value);
        var output = "";
        for(var $i = 0; $i< results.length;$i++){
        	results[$i] = results[$i].join(",");
            output +="<li>"+results[$i]+"</li>";
        }
        $("#list").html(output);
    });
});

/*Helper Clone*/
var Clone = function (data) {
    return JSON.parse(JSON.stringify(data));
}

/*Script of Search All Combinations without repetitions. Ex: [1,2,3]*/
var SearchCombinations = function (statesArray) {
    var combinations = new Array(),
        newValue = null,
        arrayBeforeLevel = new Array(),
        $level = 0,
        array = new Clone(statesArray),
        firstInteration = true,
        indexFirstInteration = 0,
        sizeValues = array.length,
        totalSizeValues = Math.pow(2, array.length) - 1;
    array.sort();
    combinations = new Clone(array);
    arrayBeforeLevel = new Clone(array);
    loopLevel: while ($level < arrayBeforeLevel.length) {
        for (var $i = 0; $i < array.length; $i++) {
            newValue = arrayBeforeLevel[$level] + "," + array[$i];
            newValue = newValue.split(",");
            newValue.sort();
            newValue = newValue.join(",");
            if (combinations.indexOf(newValue) == -1 && arrayBeforeLevel[$level].toString().indexOf(array[$i]) == -1) {
                if (firstInteration) {
                    firstInteration = false;
                    indexFirstInteration = combinations.length
                }
                sizeValues++;
                combinations.push(newValue);
                if (sizeValues == totalSizeValues) {
                    break loopLevel;
                }
            }
        }
        $level++;
        if ($level == arrayBeforeLevel.length) {
            firstInteration = true;
            arrayBeforeLevel = new Clone(combinations);
            arrayBeforeLevel = arrayBeforeLevel.splice(indexFirstInteration);
            indexFirstInteration = 0;
            $level = 0;
        }
    }
    for (var $i = 0; $i < combinations.length; $i++) {
        combinations[$i] = combinations[$i].toString().split(",");
    }
    return combinations;
}

*{font-family: Arial;font-size:14px;}
small{font-size:11px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<label for="">
    <input type="text" id="fieldArray">
    <button id="search">Search</button>
    <br><small>Info the elements. Ex: "a,b,c"</small>
</label>
<hr>
<ul id="list"></ul>