¿Cómo se genera eficientemente una lista de enteros K no repetitivos entre 0 y un límite superior N

La pregunta proporciona todos los datos necesarios: qué es un algoritmo eficiente para generar una secuencia de K enteros no repetitivos dentro de un intervalo dado [0, N-1] . El algoritmo trivial (generar números aleatorios y, antes de agregarlos a la secuencia, buscarlos para ver si ya estaban allí) es muy costoso si K es grande y está lo suficientemente cerca de N.

El algoritmo proporcionado en la selección eficiente de un conjunto de elementos aleatorios de una lista vinculada parece más complicado de lo necesario y requiere cierta implementación. Acabo de encontrar otro algoritmo que parece hacer bien el trabajo, siempre que conozca todos los parámetros relevantes, en una sola pasada.

El módulo aleatorio de la biblioteca de Python lo hace extremadamente fácil y efectivo:

from random import sample print sample(xrange(N), K) 

sample función de sample devuelve una lista de K elementos únicos elegidos de la secuencia dada.
xrange es un “emulador de lista”, es decir, se comporta como una lista de números consecutivos sin crearlo en la memoria, lo que lo hace superrápido para tareas como esta.

En The Art of Computer Programming, Volumen 2: Algoritmos Seminumerical, tercera edición , Knuth describe el siguiente algoritmo de muestreo de selección:

Algoritmo S (técnica de muestreo de selección). Para seleccionar n registros al azar de un conjunto de N, donde 0

S1. [Inicializar.] Establecer t ← 0, m ← 0. (Durante este algoritmo, m representa el número de registros seleccionados hasta el momento, yt es la cantidad total de registros de entrada que hemos tratado).

S2. [Generate U.] Genera un número aleatorio U, distribuido uniformemente entre cero y uno.

S3. [Prueba]. Si (N – t) U ≥ n – m, vaya al paso S5.

S4. [Seleccionar.] Seleccione el siguiente registro para la muestra, e incremente m y t en 1. Si m

S5. [Omitir.] Omita el siguiente registro (no lo incluya en la muestra), aumente t por 1 y vuelva al paso S2.

Una implementación puede ser más fácil de seguir que la descripción. Aquí hay una implementación de Common Lisp que selecciona n miembros aleatorios de una lista:

 (defun sample-list (n list &optional (length (length list)) result) (cond ((= length 0) result) ((< (* length (random 1.0)) n) (sample-list (1- n) (cdr list) (1- length) (cons (car list) result))) (t (sample-list n (cdr list) (1- length) result)))) 

Y aquí hay una implementación que no usa recursión, y que funciona con todo tipo de secuencias:

 (defun sample (n sequence) (let ((length (length sequence)) (result (subseq sequence 0 n))) (loop with m = 0 for i from 0 and u = (random 1.0) do (when (< (* (- length i) u) (- nm)) (setf (elt result m) (elt sequence i)) (incf m)) until (= mn)) result)) 

De hecho, es posible hacerlo en espacio proporcional a la cantidad de elementos seleccionados, en lugar del tamaño del conjunto desde el que se selecciona, independientemente de la proporción del conjunto total que seleccione. Para ello, genere una permutación aleatoria y luego seleccione de la siguiente manera:

Elija un cifrado de bloque, como TEA o XTEA. Utilice plegado XOR para reducir el tamaño del bloque a la potencia más pequeña de dos más grande que el conjunto que está seleccionando. Use la semilla aleatoria como la clave del cifrado. Para generar un elemento n en la permutación, cifra n con el cifrado. Si el número de salida no está en su conjunto, encripte eso. Repita hasta que el número esté dentro del conjunto. En promedio, tendrá que hacer menos de dos encriptaciones por número generado. Esto tiene el beneficio adicional de que si tu semilla está criptográficamente segura, también lo es tu permutación completa.

Escribí sobre esto con mucho más detalle aquí .

El siguiente código (en C, origen desconocido) parece resolver el problema extremadamente bien:

  /* generate N sorted, non-duplicate integers in [0, max[ */ int *generate(int n, int max) { int i, m, a; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; m = 0; for (i=0; i 

¿Alguien sabe dónde puedo encontrar más gems como esta?

Genera una matriz 0...N-1 llenada a[i] = i .

Luego baraja los primeros K elementos.

Arrastramiento:

  • Comience J = N-1
  • Elige un número aleatorio 0...J (di, R )
  • intercambia a[R] con a[J]
    • como R puede ser igual a J , el elemento puede intercambiarse consigo mismo
  • reste 1 de J y repita.

Finalmente, tome K últimos elementos.

Esto esencialmente selecciona un elemento aleatorio de la lista, lo mueve, luego elige un elemento aleatorio de la lista restante, y así sucesivamente.

Funciona en O (K) y O (N) tiempo, requiere O (N) almacenamiento.

La parte de mezcla se llama mezcla de Fisher-Yates o mezcla de Knuth , descrita en el 2 ° volumen de El arte de la progtwigción de computadoras.

Acelera el algoritmo trivial almacenando los números K en una tienda hash. Conocer K antes de empezar elimina toda la ineficacia de insertar en un mapa hash, y aún así obtiene el beneficio de una búsqueda rápida.

Mi solución está orientada a C ++, pero estoy seguro de que podría traducirse a otros idiomas, ya que es bastante simple.

  • Primero, genera una lista vinculada con elementos K, yendo de 0 a K
  • Entonces, siempre y cuando la lista no esté vacía, genere un número aleatorio entre 0 y el tamaño del vector
  • Tome ese elemento, empújelo en otro vector y elimínelo de la lista original

Esta solución solo involucra dos iteraciones de bucle, y ninguna búsqueda de tabla hash ni nada por el estilo. Entonces en el código real:

 // Assume K is the highest number in the list std::vector sorted_list; std::vector random_list; for(int i = 0; i < K; ++i) { sorted_list.push_back(i); } // Loop to K - 1 elements, as this will cause problems when trying to erase // the first element while(!sorted_list.size() > 1) { int rand_index = rand() % sorted_list.size(); random_list.push_back(sorted_list.at(rand_index)); sorted_list.erase(sorted_list.begin() + rand_index); } // Finally push back the last remaining element to the random list // The if() statement here is just a sanity check, in case K == 0 if(!sorted_list.empty()) { random_list.push_back(sorted_list.at(0)); } 

Paso 1: genera tu lista de enteros.
Paso 2: realiza Knuth Shuffle .

Tenga en cuenta que no necesita barajar toda la lista, ya que el algoritmo Knuth Shuffle le permite aplicar solo n combinaciones, donde n es la cantidad de elementos que debe devolver. Generar la lista todavía llevará tiempo proporcional al tamaño de la lista, pero puede reutilizar su lista existente para futuras necesidades de mezcla (suponiendo que el tamaño permanezca igual) sin necesidad de modificar la lista parcialmente mezclada antes de reiniciar el algoritmo de mezcla.

El algoritmo básico para Knuth Shuffle es que comienzas con una lista de enteros. Luego, intercambia el primer entero con cualquier número en la lista y devuelve el primer entero actual (nuevo). Luego, intercambia el segundo entero con cualquier número en la lista (excepto el primero) y devuelve el segundo entero actual (nuevo). Entonces … etc …

Este es un algoritmo absurdamente simple, pero tenga cuidado de incluir el elemento actual en la lista al realizar el intercambio o romperá el algoritmo.

La versión de Reservoir Sampling es bastante simple:

 my $N = 20; my $k; my @r; while(<>) { if(++$k <= $N) { push @r, $_; } elsif(rand(1) <= ($N/$k)) { $r[rand(@r)] = $_; } } print @r; 

Eso es $ N filas seleccionadas al azar de STDIN. Reemplace las cosas <> / $ _ con algo más si no está utilizando filas de un archivo, pero es un algoritmo bastante sencillo.

Si la lista está ordenada, por ejemplo, si desea extraer elementos K de N, pero no le importa su orden relativo, se propone un algoritmo eficiente en el documento Un algoritmo eficiente para el muestreo aleatorio secuencial (Jeffrey Scott Vitter, ACM Transactions on Mathematical Software , Vol. 13, No. 1, marzo de 1987, páginas 56-67).

editado para agregar el código en c ++ usando boost. Acabo de tipearlo y puede haber muchos errores. Los números aleatorios provienen de la biblioteca de impulso, con una semilla estúpida, así que no hagas nada serio con esto.

 /* Sampling according to [Vitter87]. * * Bibliography * [Vitter 87] * Jeffrey Scott Vitter, * An Efficient Algorithm for Sequential Random Sampling * ACM Transactions on MAthematical Software, 13 (1), 58 (1987). */ #include  #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; // This is a typedef for a random number generator. // Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand typedef boost::minstd_rand base_generator_type; // Define a random number generator and initialize it with a reproducible // seed. // (The seed is unsigned, otherwise the wrong overload may be selected // when using mt19937 as the base_generator_type.) base_generator_type generator(0xBB84u); //TODO : change the seed above ! // Defines the suitable uniform ditribution. boost::uniform_real<> uni_dist(0,1); boost::variate_generator > uni(generator, uni_dist); void SequentialSamplesMethodA(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method A. { int top=NK, S, curr=0, currsample=-1; double Nreal=N, quot=1., V; while (K>=2) { V=uni(); S=0; quot=top/Nreal; while (quot > V) { S++; top--; Nreal--; quot *= top/Nreal; } currsample+=1+S; cout << curr << " : " << currsample << "\n"; Nreal--; K--;curr++; } // special case K=1 to avoid overflow S=floor(round(Nreal)*uni()); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } void SequentialSamplesMethodD(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method D. { const int negalphainv=-13; //between -20 and -7 according to [Vitter87] //optimized for an implementation in 1987 !!! int curr=0, currsample=0; int threshold=-negalphainv*K; double Kreal=K, Kinv=1./Kreal, Nreal=N; double Vprime=exp(log(uni())*Kinv); int qu1=N+1-K; double qu1real=qu1; double Kmin1inv, X, U, negSreal, y1, y2, top, bottom; int S, limit; while ((K>1)&&(threshold S) {bottom=Nreal-Kreal; limit=NS;} else {bottom=Nreal+negSreal-1.; limit=qu1;} for(int t=N-1;t>=limit;t--) {y2*=top/bottom;top--; bottom--;} if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv)) {//Accept ! Vprime=exp(log(uni())*Kmin1inv); break; } Vprime=exp(log(uni())*Kmin1inv); } // Step D5: Select the (S+1)th record currsample+=1+S; cout << curr << " : " << currsample << "\n"; curr++; N-=S+1; Nreal+=negSreal-1.; K-=1; Kreal-=1; Kinv=Kmin1inv; qu1-=S; qu1real+=negSreal; threshold+=negalphainv; } if (K>1) {SequentialSamplesMethodA(K, N);} else { S=floor(N*Vprime); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } } int main(void) { int Ntest=10000000, Ktest=Ntest/100; SequentialSamplesMethodD(Ktest,Ntest); return 0; } $ time ./sampling|tail 

da el siguiente ouptut en mi computadora portátil

 99990 : 9998882 99991 : 9998885 99992 : 9999021 99993 : 9999058 99994 : 9999339 99995 : 9999359 99996 : 9999411 99997 : 9999427 99998 : 9999584 99999 : 9999745 real 0m0.075s user 0m0.060s sys 0m0.000s 

Este código de Ruby muestra el método de muestreo de reservorios, algoritmo R. En cada ciclo, selecciono n=5 enteros aleatorios únicos del rango [0,N=10) :

 t=0 m=0 N=10 n=5 s=0 distrib=Array.new(N,0) for i in 1..500000 do t=0 m=0 s=0 while m=nm then t=t+1 else distrib[s]+=1 m=m+1 t=t+1 end #if s=s+1 end #while if (i % 100000)==0 then puts i.to_s + ". cycle..." end end #for puts "--------------" puts distrib 

salida:

 100000. cycle... 200000. cycle... 300000. cycle... 400000. cycle... 500000. cycle... -------------- 250272 249924 249628 249894 250193 250202 249647 249606 250600 250034 

todos los números enteros entre 0-9 fueron elegidos con casi la misma probabilidad.

Es esencialmente el algoritmo de Knuth aplicado a secuencias arbitrarias (de hecho, esa respuesta tiene una versión LISP de esto). El algoritmo es O (N) en el tiempo y puede ser O (1) en la memoria si la secuencia se transmite como se muestra en la respuesta de @ MichaelCramer .

Esta es una forma de hacerlo en O (N) sin almacenamiento adicional. Estoy bastante seguro de que esta no es una distribución puramente aleatoria, pero probablemente sea lo suficientemente cerca para muchos usos.

 /* generate N sorted, non-duplicate integers in [0, max[ in O(N))*/ int *generate(int n, int max) { float step,a,v=0; int i; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; for (i=0; imax) { g[i]=max; //fix up overflow max=g[i--]-1; } return g; } 

Este es el código Perl. Grep es un filtro, y como siempre, no probé este código.

 @list = grep ($_ % I) == 0, (0..N); 
  • I = intervalo
  • N = límite superior

Solo obtenga números que coincidan con su intervalo a través del operador de módulo.

 @list = grep ($_ % 3) == 0, (0..30); 

devolverá 0, 3, 6, … 30

Este es el código pseudo Perl. Es posible que deba modificarlo para que compile.