generazione di sottoinsiemi casuali e unici

Question

Diciamo che abbiamo numeri da 1 a 25 e dobbiamo scegliere gruppi di 15 numeri.

I possibili set sono, se ho ragione 3268760.

Di quelle 3268760 opzioni, devi generare dire 100000

Quale sarebbe il modo migliore per generare 100000 unici e casuali di questi sottoinsiemi?

C'è un modo, un algoritmo per farlo?

In caso contrario, quale sarebbe l'opzione migliore per rilevare i duplicati?

Sto programmando di farlo su PHP ma una soluzione generale sarebbe sufficiente, e qualsiasi riferimento non molto "accademico" (più pratico) mi aiuterebbe molto.

Answer 1

Ecco una soluzione in PHP basata sulla risposta di mjv, che è come la pensavo. Se lo esegui per un set completo di 100.000, vedrai molte collisioni. Tuttavia, ho molta fatica a escogitare un sistema per evitarli. Invece, li controlliamo abbastanza rapidamente.

Penserò a soluzioni migliori ... su questo laptop, posso fare 10k set in 5 secondi, 20k set in meno di 20 secondi. 100k richiede alcuni minuti.

I set sono rappresentati come in (32 bit).

<?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";

Penso che sia tutto corretto, ma è tardi e mi sono goduto diverse bottiglie di birra molto belle.

Answer 2

Esiste un modo per generare un campione dei sottoinsiemi che è casuale, garantito per non avere duplicati, utilizza l'archiviazione O (1) e può essere rigenerato in qualsiasi momento. Innanzitutto, scrivi una funzione per generare una combinazione dato il suo lessico Indice . In secondo luogo, utilizzare un permutazione pseudocasuale dei primi numeri interi Combin (n, m) per scorrere le combinazioni in un ordine casuale. Inserisci semplicemente i numeri 0 ... 100000 nella permutazione, usa l'output della permutazione come input per il generatore di combinazioni ed elabora la combinazione risultante.

Answer 3

Devono essere veramente casuali? O apparentemente casuale?

Selezione: genera un set con tutti i 25 - "shuffle " i primi 15 elementi usando Fisher-Yates / the Knuth shuffle, quindi controlla se hai già visto quella permutazione dei primi 15 elementi prima. In tal caso, ignorare e riprovare.

Duplicati: hai 25 valori che ci sono o no - questo può essere banalmente cancellato su un valore intero (se è presente il 1 ° elemento, aggiungi 2 ^ 0, se il secondo è, aggiungi 2 ^ 1, ecc. - può essere rappresentato direttamente come un numero di 25 bit), quindi puoi controllare facilmente se l'hai già visto.

Avrai un bel po 'di collisioni, ma se non è un frammento critico per le prestazioni, potrebbe essere fattibile.

Answer 4

Il generatore di numeri casuali (RNG) del tuo ambiente ti fornirà numeri casuali distribuiti uniformemente in un determinato intervallo. Questo tipo di distribuzione è spesso ciò di cui hai bisogno, ad esempio se il tuo sottoinsieme simula i disegni della lotteria, ma è importante menzionare questo fatto nel caso in cui stai modellando, ad esempio l'età delle persone trovate sulla base di una scuola media ...

Dato questo RNG puoi " disegnare " 10 (o 15, leggi sotto) numeri tra 1 e 25. Ciò potrebbe richiedere di moltiplicare (e arrotondare) il numero casuale prodotto dal generatore e di ignorare i numeri che sono sopra i 25 (cioè disegnare di nuovo), a seconda del API esatta associata all'RNG, ma ottenere di nuovo un disegno in un determinato intervallo è banale. Dovrai anche ridisegnare quando compare di nuovo un numero.

Ti suggerisco di ottenere solo 10 numeri, poiché questi possono essere rimossi dalla sequenza completa 1-25 per produrre un set di 15. In altre parole, il disegno 15 da inserire è lo stesso disegno 10 da estrarre ...

Successivamente è necessario affermare l'unicità dei set. Invece di archiviare l'intero set, è possibile utilizzare un hash per identificare ciascun set in modo univoco. Questo dovrebbe richiedere meno di 25 bit, quindi può essere memorizzato su un numero intero di 32 bit. È quindi necessario disporre di una memoria efficiente per un massimo di 100.000 di questi valori; a meno che non si desideri archiviarlo in un database.

Su questa domanda di unicità di 100.000 set estratti da tutti i set possibili, la probabilità di una collisione sembra relativamente bassa. Modifica: Oops ... Ero ottimista ... Questa probabilità non è così bassa, con circa l'1,5% di probabilità di una collisione che inizia dopo aver pescato il 50.000esimo, ci saranno parecchie collisioni, abbastanza da garantire un sistema per escluderle ...