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

En El Arte de la Programación Informática, Volumen 2: Algoritmos Seminuméricos, 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. [Inicialización.] Conjunto t ← 0, m ← 0. (Durante este algoritmo, m representa el número de registros seleccionados hasta ahora, y t es el número total de registros de entrada que hemos tratado con.)

S2. [Generar U.] Generar un número aleatorio U, uniformemente distribuido 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 y aumente m y t en 1. Si m

S5. [Saltar.] Omita el siguiente registro (no lo incluya en la muestra), aumente t en 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) 
                   (- n m))
            (setf (elt result m) (elt sequence i))
            (incf m))
       until (= m n))
    result))

En realidad es posible hacer esto en espacio proporcional al número de elementos seleccionados, en lugar del tamaño del conjunto que está seleccionando, independientemente de la proporción del conjunto total que esté seleccionando. Esto se hace generando una permutación aleatoria, luego seleccionando de ella de la siguiente manera:

Elija un cifrado por bloques, como TEA o XTEA. Utilice XOR folding 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. Utilice el semilla aleatoria como la clave para el cifrado. Para generar un elemento n en la permutación, cifrar n con el cifrado. Si el número de salida no está en su conjunto, cifrar eso. Repita hasta que el número esté dentro del set. En promedio, tendrá que hacer menos de dos cifrados por número generado. Esto tiene el beneficio adicional de que si su semilla es criptográficamente segura, también lo es toda su permutación.

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<max; i++) {
        a = random_in_between(0, max - i);
        if (a < n - m) {
            g[m] = i;
            m ++;
        }
    }
    return g;
 }

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

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

Luego baraja los primeros elementos K.

Barajando:

• Start J = N-1
• Elige un número aleatorio 0...J (digamos, R)
• intercambiar a[R] con a[J]
  • dado que R puede ser igual a J, el elemento puede intercambiarse consigo mismo
• resta 1 de J y repite.

Finalmente, toma K los últimos elementos.

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

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

La parte de barajar se llama Fisher-Yates shuffle o Knuth's shuffle , descrito en el 2do volumen de El Arte de la Programación de Computadoras.

Acelere el algoritmo trivial almacenando los números K en un almacén de hash. Conocer K antes de comenzar elimina toda la ineficiencia 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, genere una lista enlazada con K elementos, yendo de 0 a K
• Entonces, mientras la lista no esté vacía, genere un número aleatorio entre 0 y el tamaño del vector
• Tome ese elemento, empújelo a otro vector y elimínelo de la lista original

Esta solución solo implica dos iteraciones de bucle, y no hay búsquedas de tabla hash o cualquier cosa por el estilo. Así que en el código real:

// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> 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: Genere su lista de enteros.
Paso 2: Realizar Barajar Knuth.

Tenga en cuenta que no necesita barajar toda la lista, ya que el algoritmo de barajar Knuth le permite aplicar solo n barajar, donde n es el número de elementos a devolver. La generación de la lista todavía llevará tiempo proporcional al tamaño de la lista, pero puede reutilizar su lista existente para cualquier necesidad futura de barajar (suponiendo que el tamaño se mantenga igual) sin necesidad de preshuffle el parcialmente lista barajada antes de reiniciar el algoritmo de barajado.

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

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 muestreo de Reservorios 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 N filas seleccionadas aleatoriamente de STDIN. Reemplace las cosas / _ _ con otra cosa si no está utilizando filas de un archivo, pero es un algoritmo bastante sencillo.

Si la lista está ordenada, por ejemplo, si desea extraer K elementos 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, March 1987, Pages 56-67.).

Editado para agregar el código en c++ usando boost. Acabo de escribirlo y puede haber muchos errores. El los números aleatorios vienen de la biblioteca boost, 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 <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>

#include <iomanip>

#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>

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<base_generator_type&, boost::uniform_real<> > 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=N-K, 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<N))
        {
        Kmin1inv=1./(Kreal-1.);
        while(1)
            {//Step D2: generate X and U
            while(1)
                {
                X=Nreal*(1-Vprime);
                S=floor(X);
                if (S<qu1) {break;}
                Vprime=exp(log(uni())*Kinv);
                }
            U=uni();
            negSreal=-S;
            //step D3: Accept ?
            y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
            Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
            if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
            //step D4 Accept ?
            y2=0; top=Nreal-1.;
            if (K-1 > S)
                {bottom=Nreal-Kreal; limit=N-S;}
            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 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 Ruby muestra el método de Muestreo de Reservorios, Algoritmo R. En cada ciclo, selecciono n=5 enteros aleatorios únicos de [0,N=10) rango:

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<n do

  u=rand()
  if (N-t)*u>=n-m 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 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 el la secuencia se transmite como se muestra en la respuesta de@MichaelCramer.

Aquí hay una manera de hacerlo en O(N) sin almacenamiento adicional. Estoy bastante seguro de que esto no es una distribución puramente aleatoria, pero es probablemente 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; i<n; i++) {
        step = (max-v)/(float)(n-i);
        v+ = floating_pt_random_in_between(0.0, step*2.0);
        if ((int)v == g[i-1]){
          v=(int)v+1;             //avoid collisions
        }
        g[i]=v;
    }
    while (g[i]>max) {
      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 he probado 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

Esto es código pseudo Perl. Es posible que necesite retocarlo para que se compile.