combinazione senza ripetizione di N elementi, senza uso for..to..do

StackOverflow https://stackoverflow.com/questions/8316479

Domanda

voglio carico in un elenco la combinazione del numero N senza ripetizione, dando per inserire gli elementi e di gruppo. Ad esempio, con 4 elementi [1,2,3,4], ho per: 

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]

Ora, ho risolto utilizzando ciclo nidificato per, ad esempio con il gruppo 2, scrivo: 

  for x1 := 1 to 3 do
    for x2 := Succ(x1) to 4 do
      begin
        // x1, x2 // 
      end

o per il gruppo 3, ho scritto: 

  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

e così per gli altri gruppi. In generale, se voglio farlo per il gruppo N, come posso fare, senza scrittura procedure N con cicli annidati? Ho pensata ad un doppio anello while..do uno da utilizzare per il contatore e uno da utilizzare per contare i gruppi, ma lo è anche po 'difficile, volevo sapere se c'era qualche soluzione più semplice e veloce, anche utilizzando booleano operatore o qualcosa di così . Chi mi può dare qualche suggerire in proposito? Grazie mille.

È stato utile?

Soluzione

Sembra siete alla ricerca di un algoritmo veloce per calcolare tutte le k-combinazioni. Il seguente codice di Delphi è una traduzione diretta del codice C trovate qui: Generazione combinazioni . Ho anche corretto un bug in quel codice! 

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}

Altri suggerimenti

Ecco una piuttosto divertente soluzione affidamento su bitsets. Così com'è è limitato a gruppi di dimensione non superiore a 32. Io non credo che sia una limitazione pratica perché ci sono un molto di sottoinsiemi di un insieme di cardinalità maggiore di 32.

L'uscita non è nell'ordine che si vuole, ma che sarebbe stato abbastanza facile per porre rimedio, se è importante per voi. 

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}

E qui è una variante che solo elenca i sottoinsiemi di un cardinalità specificato: 

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}

Questa sembra essere una domanda che si apre più e più e un paio di pezzi di codice sono calci su questo indirizzo il problema. Un bel algoritmo in codice è stato scritto, ma non era assolutamente pulita C e non portabile su UNIX o Linux o qualsiasi sistema POSIX, perciò ho ripulito tutto e ha aggiunto messaggi di avviso, l'uso e la capacità di fornire una dimensione set e dimensioni sub_set sulla linea di comando. Anche pettine [] ha stata convertita nella puntatore più generale a un array di numeri interi e calloc usato a zero la memoria necessaria per qualsiasi set di dimensioni uno può desiderare.

Di seguito è ISO IEC 9899: 1999 C pulita: 

/*********************************************************************
 * 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 dclarke@blastwave.org  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 );

}

Uno può compilare sopra su una macchina basata Opteron così: 

$ 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

Un test banale pratica con un set di 10 e un sub-insieme di 6 sarà così: 

$ ./combinations 10 6 | wc -l 
210

La matematica è corretta: 

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

Ora che il pettine array intero si basa su un sistema di puntamento si sono limitate solo dalla memoria e tempo a disposizione. Quindi abbiamo la seguente: 

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

Questo è corretto: 

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

Possiamo ora spingere i limiti un po 'così: 

$ ./combinations 30 24 | wc -l 
593775

Anche in questo caso la matematica è d'accordo con il risultato: 

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

Sentitevi liberi di spingere i limiti del sistema: 

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

Devo ancora provare qualcosa di più grande, ma gli sguardi di matematica corretta così come l'uscita finora. Sentitevi liberi di farmi sapere se è necessaria qualche correzione.

Dennis Clarke dclarke@blastwave.org 28 dicembre 2012

A meno che non è possibile effettuare chiamate di funzione da qualche requisito, fare questo: 

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);
    }
}

Hai davvero bisogno di un qualche tipo di ricorsione perché è necessario per la memorizzazione automatica dei risultati intermedi. Fatemi sapere se c'è requisito speciale che rende questa soluzione non funzionano.

In seguito il link che David ha registrato e cliccando in giro mi ha portato a un articolo in cui si coniare il termine "banchiere Ricerca", che sembra adattarsi il vostro modello.

L'articolo fornisce una soluzione ad esempio in C ++, ricorsione utilizza:

efficiente enumerazione i sottoinsiemi di un insieme

Ho creato questo script qui e ha lavorato molto bene: 

$(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>

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top