php - print permutations in c

generación de subconjuntos aleatorios y únicos

Question

Digamos que tenemos números del 1 al 25 y tenemos que elegir conjuntos de 15 números.

Los posibles conjuntos son, si estoy en lo cierto 3268760.

De esas 3268760 opciones, tienes que generar decir 100000

¿Cuál sería la mejor manera de generar 100000 únicos y aleatorios de esos subconjuntos?

¿Hay alguna manera, un algoritmo para hacer eso?

Si no, ¿cuál sería la mejor opción para detectar duplicados?

Estoy planeando hacer esto en PHP pero una solución general sería suficiente, y cualquier referencia que no sea mucho ''académica'' (más práctica) me ayudaría mucho.

Answer 1

¿Tienen que ser realmente al azar? ¿O aparentemente aleatorio?

Selección: genera un conjunto con todos los 25 - "mezcla" los primeros 15 elementos usando Fisher-Yates / Knuth shuffle, y luego verifica si has visto esa permutación de los primeros 15 elementos antes. Si es así, descarte y vuelva a intentarlo.

Duplicados: tiene 25 valores que están allí o no; esto se puede dividir trivialmente en un valor entero (si el primer elemento está presente, agregue 2 ^ 0, si el segundo es, agregue 2 ^ 1, etc.) puede ser representado directamente como un número de 25 bits), por lo que puede verificar fácilmente si ya lo ha visto.

Obtendrá un buen número de colisiones, pero si no es un fragmento crítico de rendimiento, podría ser factible.

Answer 2

Aquí hay una solución en PHP basada en la respuesta de mjv, que es cómo estaba pensando en ello. Si lo ejecuta por 100k sets completos, de hecho verá muchas colisiones. Sin embargo, estoy en la imposibilidad de diseñar un sistema para evitarlos. En cambio, simplemente los revisamos con bastante rapidez.

Pensaré en mejores soluciones ... en esta computadora portátil, puedo hacer 10k sets en 5 segundos, 20k sets en menos de 20 segundos. 100k lleva varios minutos.

Los conjuntos se representan como entradas de (32 bits).

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

Creo que todo es correcto, pero es tarde y he disfrutado de varias botellas de cerveza muy buenas.

Answer 3

El generador de números aleatorios (RNG) de su entorno le proporcionará números aleatorios que están distribuidos uniformemente en un rango particular. Este tipo de distribución es a menudo lo que se necesita, por ejemplo, si su subconjunto simula dibujos de lotería, pero es importante mencionar este hecho en caso de que esté modelando, digamos la edad de las personas que se encuentran en la escuela secundaria ...

Dado este RNG puedes "dibujar" 10 (o 15, leer a continuación) números entre 1 y 25. Esto puede requerir que multiplique (y redondee) el número aleatorio producido por el generador, y que ignore los números que están por encima de 25 ( es decir, dibujar de nuevo), dependiendo de la API exacta asociada con el RNG, pero volver a obtener un dibujo en un rango dado es trivial. También necesitará volver a dibujar cuando vuelva a aparecer un número.

Te sugiero que obtengas 10 números solamente, ya que se pueden eliminar de la secuencia completa de 1 a 25 para producir un conjunto de 15. En otras palabras, dibujar 15 para poner es el mismo dibujo 10 para sacar ...

A continuación, debe afirmar la singularidad de los conjuntos. En lugar de almacenar todo el conjunto, puede usar un hash para identificar cada conjunto de manera única. Esto debería tomar menos de 25 bits, por lo que se puede almacenar en un entero de 32 bits. Entonces necesita tener un almacenamiento eficiente para hasta 100,000 de estos valores; a menos que desee almacenar esto en una base de datos.

Sobre la cuestión de la unicidad de 100.000 conjuntos tomados de todos los conjuntos posibles, la probabilidad de una colisión parece relativamente baja. Edit: Oops ... era optimista ... Esta probabilidad no es tan baja, con un 1.5% de probabilidad de que una colisión comience después de dibujar el 50,000, habrá bastantes colisiones, suficientes para garantizar un sistema que las excluya ...

Answer 4

Hay una manera de generar una muestra de los subconjuntos que es aleatoria, se garantiza que no tendrá duplicados, se usa O (1) almacenamiento y se puede volver a generar en cualquier momento. Primero, escribe una función para generar una combinación dado su índice léxico . Segundo, use una permutación pseudoaleatoria de los primeros enteros de Combin (n, m) para pasar por esas combinaciones en un orden aleatorio. Simplemente introduzca los números 0 ... 100000 en la permutación, use la salida de la permutación como entrada al generador de combinación y procese la combinación resultante.