Kombination ohne Wiederholung von N -Elementen ohne Gebrauch für.. to..do

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

Frage

Ich möchte in einer Liste die Kombination von N -Nummer ohne Wiederholung laden, die den Elementen und der Gruppe eingibt. Zum Beispiel mit 4 Elementen [1,2,3,4] habe ich für:

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]

Jetzt habe ich es mit einer verschachtelten Schleife gelöst, beispielsweise mit Gruppe 2, schreibe ich:

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

Oder für Gruppe 3 schrieb ich:

  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

und so für andere Gruppen. Im Allgemeinen, wenn ich es für Gruppe n tun möchte, wie ich kann, ohne Schreiben n Verfahren mit verschachtelten Schleifen? Ich habe zu einem Doppel nachgedacht. . Wer kann mir ein paar Vorschläge dazu geben? Vielen Dank.

War es hilfreich?

Lösung

Es scheint, dass Sie nach einem schnellen Algorithmus suchen, um alle K-Kombinationen zu berechnen. Der folgende Delphi -Code ist eine direkte Übersetzung des hier gefundenen C -Codes: Kombinationen erzeugen. Ich habe sogar einen Fehler in diesem Code behoben!

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.

Ausgabe

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

Andere Tipps

Hier ist eine ziemlich lustige Lösung, die auf Bitsets angewiesen ist. Wie es aussieht, ist es auf Größe von nicht mehr als 32 beschränkt. Ich denke nicht, dass dies eine praktische Einschränkung ist, da es a gibt viel von Teilmengen für eine Reihe von Kardinalität von mehr als 32.

Die Ausgabe ist nicht in der gewünschten Reihenfolge, aber das wäre einfach genug, wenn es Ihnen wichtig ist.

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.

Ausgabe

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

Und hier ist eine Variante, die nur die Teilmengen einer bestimmten Kardinalität auflistet:

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.

Ausgabe

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

Dies scheint eine Frage zu sein, die immer und immer wieder auftaucht und ein paar Code -Teile dieses Problems über das Problem treten. Ein sehr schöner Algorithmus in einem Code wurde geschrieben, aber er war nicht streng sauber c und nicht über Unix oder Linux oder ein POSIX -System tragbar. Daher habe ich ihn aufgeräumt und Warnmeldungen, Verwendung und die Fähigkeit, eine festgelegte Größe und eine festgelegte Größe zu liefern, hinzugefügt. sub_set Größe in der Befehlszeile. Auch Comb [] wurde zu einem allgemeineren Zeiger auf eine Reihe von Ganzzahlen umgestellt und CALLOC verwendet, um den Speicher zu null, der für die gewünschte festgelegte Größe benötigt wird.

Das Folgende ist ISO IEC 9899: 1999 C sauber: 

/*********************************************************************
 * 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 );

}

Man kann das oben genannte auf einer auf Oppteron -basierten Maschine zusammenstellen. 

$ 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

Ein schneller trivialer Test mit einer festgelegten Größe von 10 und einem Untereinsatz von 6 ist daher: 

$ ./combinations 10 6 | wc -l 
210

Die Mathematik ist richtig: 

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

Nachdem der Integer -Array -Kamm auf einem Zeigersystem basiert, sind wir nur durch den verfügbaren Speicher und die verfügbare Zeit eingeschränkt. Deshalb haben wir Folgendes: 

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

Das sieht richtig aus: 

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

Wir können jetzt die Grenzen ein wenig überschreiten: 

$ ./combinations 30 24 | wc -l 
593775

Wieder stimmt die Mathe mit dem Ergebnis überein: 

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

Fühlen Sie sich frei, die Grenzen Ihres Systems zu überschreiten:

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

Ich habe noch nichts Größeres ausprobiert, aber die Mathematik sieht sowohl korrekt als auch die bisherige Ausgabe aus. Fühlen Sie sich frei, mich wissen zu lassen, ob eine Korrektur erforderlich ist.

Dennis Clarke dclarke@blastwave.org 28. Dezember 2012

Wenn Sie keine Funktionsaufrufe nach einer Anforderung machen können, tun Sie Folgendes:

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

Sie benötigen wirklich eine Art Rekursion, da Sie einen automatischen Speicher für Zwischenergebnisse benötigen. Lassen Sie mich wissen, ob es eine besondere Anforderung gibt, die diese Lösung nicht funktioniert.

Nach dem Link, den David gepostet hat, und das Klicken zu haben, führte mich zu einem Artikel, in dem sie den Begriff "Banker's Search" einbrachten, der zu Ihrem Muster zu passen scheint.

Der Artikel enthält eine Beispiellösung in C ++ unter Verwendung einer Rekursion:

Effizient Aufzistung der Teilmengen eines Satzes

Ich habe dieses Skript hier erstellt und sehr gut gearbeitet:

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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top