¿Cómo se genera eficientemente una lista de K enteros no repetidos entre 0 y un límite superior N [duplicado]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esta pregunta ya tiene respuesta aquí:
- ¿Números aleatorios únicos (no repetidos) en O (1)? 21 respuestas
La pregunta proporciona todos los datos necesarios:¿Cuál es un algoritmo eficiente para generar una secuencia de k números enteros que no se repiten 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 lo suficientemente cerca para norte.
El algoritmo proporcionado en Seleccionar eficientemente 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 funcionar bien, siempre que conozca todos los parámetros relevantes, de una sola pasada.
Solución
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 devuelve una lista de K elementos únicos elegidos de la secuencia dada.
xrange es un " list emulator " ;, es decir, se comporta como una lista de números consecutivos sin crearlo en la memoria, lo que lo hace súper rápido para tareas como esta.
Otros consejos
En El arte de la programación de computadoras, Volumen 2: Algoritmos seminé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 & Lt; n & # 8804; N.
S1. [Inicializar.] Establezca t & # 8592; 0, m & # 8592; 0. (Durante este algoritmo, m representa el número de registros seleccionados hasta el momento, y t es el número total de registros de entrada con los que hemos tratado).
S2. [Generar U.] Genere un número aleatorio U, distribuido uniformemente entre cero y uno.
S3. [Prueba.] If (N & # 8211; t) U & # 8805; n & # 8211; m, vaya al paso S5.
S4. [Seleccionar.] Seleccione el siguiente registro para la muestra y aumente m y t en 1. Si m & Lt; n, vaya al paso S2; de lo contrario, la muestra está completa y el algoritmo termina.
S5. [Omitir] Omita el siguiente registro (no lo incluya en la muestra), aumente t en 1 y regrese 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 utiliza la recursividad 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 un 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. Para ello, genera una permutación aleatoria y luego selecciona de esta forma:
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, encripte n con el cifrado. Si el número de salida no está en su conjunto, cifre 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 su semilla es criptográficamente segura, también lo es su 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<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?
Generar una matriz 0...N-1 completado a[i] = i.
Luego baraja el primero K elementos.
Arrastramiento:
- Comenzar
J = N-1 - Elige un número aleatorio
0...J(decir,R) - intercambio
a[R]cona[J]- desde
Rpuede ser igual aJ, el elemento puede intercambiarse consigo mismo
- desde
- sustraer
1deJy repetir.
Finalmente, toma K últimos elementos.
Básicamente, esto selecciona un elemento aleatorio de la lista, lo saca, luego selecciona un elemento aleatorio de la lista restante, y así sucesivamente.
Trabaja en DE ACUERDO) y EN) tiempo, requiere EN) almacenamiento.
La parte de barajar se llama Mezcla de Fisher-Yates o La mezcla de Knuth, descrito en el segundo volumen de El arte de la programación informática.
Acelere el algoritmo trivial almacenando los números K en una tienda de hashing. Saber K antes de comenzar le quita toda la ineficiencia de insertar en un mapa hash, y aún 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 vinculada con elementos K, pasando 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, introdúzcalo en otro vector y retírelo de la lista original
Esta solución solo implica dos iteraciones de bucle, y no hay búsquedas de tablas hash ni nada por el estilo. Entonces, 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: Genera tu lista de enteros.
Paso 2: Realice Knuth Shuffle .
Tenga en cuenta que no necesita barajar la lista completa, ya que el algoritmo Knuth Shuffle le permite aplicar solo n barajas, donde n es el número de elementos a devolver. La generación de la lista todavía tomará un 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 permanezca igual) sin necesidad de mezclar previamente la lista barajada parcialmente 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 (nuevo) actual. 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 muestreo de yacimientos 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 & Lt; & Gt; / $ _ con algo más si no está usando 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 secuencial aleatorio (Jeffrey Scott Vitter, Transacciones ACM en software matemático , Vol. 13, No. 1, marzo de 1987, páginas 56-67.).
editado para agregar el código en c ++ usando boost. Lo acabo de escribir 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 <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
ofrece la siguiente salida 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 Ruby muestra el método Muestreo de yacimientos, 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 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 @MichaelCramer's answer .
Aquí hay una manera 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 cercana 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 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 se compile.
