zufällige und einzigartige Untergruppen Generation

Question

Hier kann sagen, wir haben Zahlen von 1 bis 25 und wir müssen Sätze von 15 Zahlen wählen.

Die möglichen Sets sind, wenn ich mich richtig 3.268.760.

Von den 3268760 Optionen, müssen Sie erzeugen sagen 100000

Was wäre der beste Weg, 100000 einzigartig und zufällige diese Teilmengen zu generieren?

Gibt es eine Möglichkeit, ein Algorithmus, das zu tun?

Wenn nicht, was wäre die beste Option sein, um Duplikate zu erkennen?

Ich plane dies auf PHP zu tun, sondern eine allgemeine Lösung wäre genug, und jede Bezugnahme nicht zu viel ‚akademische‘ (praktische) würde mir helfen, eine Menge.

Answer 1

Hier ist eine Lösung in PHP basierend auf mjv Antwort, die ist, wie ich darüber dachte. Wenn Sie es für ein volles 100k-Sets ausführen, sehen Sie in der Tat eine Menge von Kollisionen. Allerdings bin ich ein System schwer zu entwickeln, sie zu vermeiden. Stattdessen haben wir sie nur ziemlich schnell überprüfen.

Ich werde über bessere Lösungen denkt ... auf diesem Laptop, ich 10k-Sets in 5 Sekunden tun können, 20k-Sets in weniger als 20 Sekunden. 100k dauert einige Minuten.

Die Sätze werden als (32-Bit) Ints vertreten.

<?PHP
    /* (c) 2009 tim - anyone who finds a use for this is very welcome to use it with no restrictions unless they're making a weapon */

    //how many sets shall we generate?
    $gNumSets = 1000;

    //keep track of collisions, just for fun.
    $gCollisions = 0;

    $starttime = time();

    /**
     * Generate and return an integer with exactly 15 of the lower 25 bits set (1) and the other 10 unset (0)
     */ 
    function genSetHash(){
      $hash = pow(2,25)-1;

      $used = array();

      for($i=0;$i<10;){

        //pick a bit to turn off
        $bit = rand(0,24);

        if (! in_array($bit,$used)){
          $hash =  ( $hash & ~pow(2,$bit) );
          $i++;  
          $used[] = $bit;  
        }
      }
      return  $hash;
    }

    //we store our solution hashes in here.  
    $solutions = array();

    //generate a bunch of solutions.
    for($i=0;$i<$gNumSets;){
      $hash = genSetHash(); 

      //ensure no collisions
      if (! in_array($hash,$solutions)){
        $solutions[] = $hash;
        //brag a little.
        echo("Generated $i random sets in " . (time()-$starttime) . " seconds.\n");
        $i++;
      }else { 
        //there was a collision. There will generally be more the longer the process runs.
        echo "thud.\n"; 
        $gCollisions++;
      }
    }

    // okay, we're done with the hard work.  $solutions contains a bunch of
    // unique, random, ints in the right range.  Everything from here on out
    // is just output.

    //takes an integer with 25 significant digits, and returns an array of 15 numbers between 1 and 25
    function hash2set($hash){
      $set = array();
      for($i=0;$i<24;$i++){  
        if ($hash & pow(2,$i)){
          $set[] = $i+1;
        }
      }
      return $set;
    }

    //pretty-print our sets.
    function formatSet($set){
      return "[ " . implode(',',$set) . ']';
    }

    //if we wanted to print them, 
    foreach($solutions as $hash){
      echo formatSet(hash2set($hash)) . "\n";
    }

    echo("Generated $gNumSets unique random sets in " . (time()-$starttime) . " seconds.\n");

    echo "\n\nDone.  $gCollisions collisions.\n";

Ich denke, es ist alles richtig, aber es ist zu spät, und ich habe einige sehr schöne Flaschen Bier genossen.

Answer 2

Es gibt eine Möglichkeit, eine Probe der Untergruppen zu erzeugen, die zufällig ist, garantiert nicht die Duplikate haben, verwendet O (1) Lagerung und neu erzeugt jederzeit werden kann. Zuerst schreiben Sie eine Funktion seine lexikalische eine Kombination gegeben erzeugen Index . Zweitens verwenden Sie einen Pseudo-Zufalls-Permutation der ersten Combin (n, m) ganzen Zahlen durch diese Kombinationen in einer zufälligen Reihenfolge zu treten. Einfach die Zahlen 0 füttern ... 100000 in die Permutation, die Ausgabe der Permutation als Eingabe in der Generator-Kombination verwenden, und die resultierende Kombination verarbeiten.

Answer 3

Müssen sie wirklich zufällig sein? Oder scheinbar zufällig?

Auswahl: erzeugt einen Satz mit allen 25 - „shuffle“ die ersten 15 Elementen unter Verwendung von Fisher-Yates / die Knuth Shuffle, und dann prüfen, ob Sie vor, dass die Permutation der ersten 15 Elemente gesehen haben. Wenn ja, außer Acht lassen und erneut versuchen kann.

Dubletten: Sie haben 25 Werte, die es gibt oder nicht - das kann trivialerweise auf einen ganzzahligen Wert gehasht werden (wenn das erste Element vorhanden ist, fügen 2 ^ 0, wenn das zweite ist, fügen Sie 2 ^ 1 usw. - es kann direkt als 25-Bit-Zahl) dargestellt werden, so können Sie leicht überprüfen, ob Sie es schon gesehen haben.

Sie werden ein gutes Stück von Kollisionen, aber wenn es nicht eine Leistung kritisch Schnipsel ist, könnte es machbar sein.

Answer 4

Der Zufallszahlengenerator (RNG) Ihrer Umgebung finden Sie Zufallszahlen liefern, die in einem bestimmten Bereich gleichmäßig verteilt sind. Diese Art der Verteilung ist oft das, was benötigt wird, sagen, wenn Ihre Teilmengen Lottoziehungen simulieren, aber es ist wichtig, diese Tatsache im Fall IhrDeterm modelliert das Alter der Personen auf dem Gelände einer Mittelschule ...

Dieses RNG Da können Sie „ziehen“ 10 (oder 15, lesen Sie weiter unten) Zahlen zwischen 1 und 25. Dies kann verlangen, dass Sie mehrfach (und rund) die Zufallszahl vom Generator erzeugt wird, und dass Sie Zahlen ignorieren, die oberhalb von 25 (dh zeichnet wieder), abhängig von der genauen API mit dem RNG verbunden ist, aber wieder eine Zeichnung in einem gegebenen Bereich ist immer trivial. Sie werden auch neu zeichnen müssen, wenn eine Zahl wieder aufkommt.

Ich schlage vor, Sie 10 Zahlen nur bekommen, da diese von der 1-25 vollständige Sequenz entfernt werden kann, einen Satz von 15. Mit anderen Worten zu produzieren 15 Zeichnung in setzen ist die gleiche Zeichnung 10 herauszunehmen ...

Als Nächstes werden Sie die Einzigartigkeit der Sätze behaupten müssen. Anstatt den ganzen Satz zu speichern, kann man einen Hash verwenden, um jeweils eindeutig festgelegt zu identifizieren. Dies sollte weniger, dass 25 Bits nehmen, so kann auf eine 32-Bit-Integer gespeichert werden. Sie müssen dann für bis zu 100.000 dieser Werte eine effiziente Speicherung haben; es sei denn, Sie in einer Datenbank diese gespeichert werden sollen.

Auf dieser Frage der Einzigartigkeit von 100.000 Sätzen aus allen möglichen Mengen genommen, scheint die Wahrscheinlichkeit einer Kollision relativ gering. Edit: Ups ... ich war optimistisch, ... Diese Wahrscheinlichkeit ist nicht so niedrig, mit etwa 1,5% Chance einer Kollision beginnend nach den 50.000sten zeichnen, wird es ziemlich viele Kollisionen, genug, um ein System zu rechtfertigen, sie auszuschließen ...