Como você gera com eficiência uma lista de números inteiros que não repetem entre 0 e um limite superior n [duplicado
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Esta pergunta já tem uma resposta aqui:
A pergunta fornece todos os dados necessários: o que é um algoritmo eficiente para gerar uma sequência de K números inteiros não repetidos dentro de um determinado intervalo 0, N-1. O algoritmo trivial (gerando números aleatórios e, antes de adicioná -los à sequência, olhando -os para ver se eles já estavam lá) é muito caro se K é grande e próximo o suficiente para N.
O algoritmo fornecido em Selecionando com eficiência um conjunto de elementos aleatórios de uma lista vinculada parece mais complicado do que o necessário e requer alguma implementação. Acabei de encontrar outro algoritmo que parece fazer o trabalho bem, desde que você conheça todos os parâmetros relevantes, em um único passe.
Solução
o módulo aleatório Da Biblioteca Python torna extremamente fácil e eficaz:
from random import sample
print sample(xrange(N), K)
sample A função retorna uma lista de k elementos exclusivos escolhidos na sequência fornecida.
xrange é um "emulador de lista", ou seja, ele se comporta como uma lista de números consecutivos sem criá-lo na memória, o que o torna super-rápido para tarefas como esta.
Outras dicas
Dentro A arte da programação de computadores, volume 2: algoritmos seminuméricos, terceira edição, Knuth descreve o seguinte algoritmo de amostragem de seleção:
Algoritmo S (técnica de amostragem de seleção). Para selecionar N registros aleatoriamente de um conjunto de n, onde 0 <n ≤ n.
S1. [Initialize.] Definir t ← 0, M ← 0. (Durante este algoritmo, M representa o número de registros selecionados até agora, e T é o número total de registros de entrada com os quais lidamos.)
S2. [Gere U.] Gere um número aleatório U, distribuído uniformemente entre zero e um.
S3. [Teste.] Se (n - t) u ≥ n - m, vá para a etapa S5.
S4. [SELECT.] Selecione o próximo registro para a amostra e aumente M e T em 1. Se m <n, vá para a etapa S2; Caso contrário, a amostra está completa e o algoritmo termina.
S5. [Pule.] Pule o próximo registro (não o inclua na amostra), aumente t em 1 e volte para a etapa S2.
Uma implementação pode ser mais fácil de seguir do que a descrição. Aqui está uma implementação LISP comum que seleciona n membros aleatórios de uma 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))))
E aqui está uma implementação que não usa recursão e que funciona com todos os tipos de seqüências:
(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))
É realmente possível fazer isso no espaço proporcional ao número de elementos selecionados, em vez do tamanho do conjunto que você está selecionando, independentemente da proporção do conjunto total que você está selecionando. Você faz isso gerando uma permutação aleatória e selecionando assim:
Escolha uma cifra de bloco, como CHÁ ou XTEA. Usar Dobrar xor Para reduzir o tamanho do bloco para a menor potência de dois maiores que o conjunto que você está selecionando. Use a semente aleatória como a chave para a cifra. Para gerar um elemento n na permutação, criptografar n com a cifra. Se o número de saída não estiver no seu conjunto, criptografará isso. Repita até que o número esteja dentro do conjunto. Em média, você terá que fazer menos de duas criptografias por número gerado. Isso tem o benefício adicional de que, se sua semente for criptograficamente segura, também é toda a sua permutação.
Eu escrevi sobre isso com muito mais detalhes aqui.
O código a seguir (em C, origem desconhecida) parece resolver o problema extremamente bem:
/* 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;
}
Alguém sabe onde posso encontrar mais jóias como esta?
Gerar uma matriz 0...N-1 preenchidas a[i] = i.
Então embaralhe o primeiro K Itens.
Shuffling:
- Começar
J = N-1 - Escolha um número aleatório
0...J(dizer,R) - troca
a[R]coma[J]- desde
Rpode ser igual aJ, o elemento pode ser trocado por si mesmo
- desde
- subtrair
1a partir deJe repita.
Finalmente, pegue K Últimos elementos.
Isso essencialmente escolhe um elemento aleatório da lista, o move e escolhe um elemento aleatório da lista restante e assim por diante.
Trabalha em OK) e SOBRE) tempo, requer SOBRE) armazenar.
A parte de embaralhamento é chamada Fisher-Yates Shuffle ou Knuth's Shuffle, descrito no segundo volume de A arte da programação de computadores.
Acelere o algoritmo trivial, armazenando os K números em uma loja de hash. Conhecer K antes de começar tira toda a ineficiência de inserir um mapa de hash e você ainda obtém o benefício de uma pesquisa rápida.
Minha solução é orientada para C ++, mas tenho certeza de que pode ser traduzida para outros idiomas, pois é bem simples.
- Primeiro, gerar uma lista vinculada com K Elements, passando de 0 para K
- Então, desde que a lista não esteja vazia, gerar um número aleatório entre 0 e o tamanho do vetor
- Pegue esse elemento, empurre -o para outro vetor e remova -o da lista original
Esta solução envolve apenas duas iterações de loop e nenhuma pesquisa de tabela de hash ou qualquer coisa do tipo. Então, no 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));
}
Etapa 1: Gere sua lista de números inteiros.
Etapa 2: execute Knuth Shuffle.
Observe que você não precisa embaralhar a lista inteira, pois o algoritmo Knuth Shuffle permite aplicar apenas n shuffles, onde n é o número de elementos para retornar. A geração da lista ainda levará tempo proporcional ao tamanho da lista, mas você pode reutilizar sua lista existente para futuras necessidades de embaralhamento (assumindo que o tamanho permaneça o mesmo) sem a necessidade de pré -abastecer a lista parcialmente embaralhada antes de reiniciar o algoritmo de embaralhamento.
O algoritmo básico para Knuth Shuffle é que você começa com uma lista de números inteiros. Em seguida, você troca o primeiro número inteiro com qualquer número da lista e retorna o primeiro (novo) primeiro número inteiro. Em seguida, você troca o segundo número inteiro com qualquer número na lista (exceto a primeira) e retorna o segundo número atual (novo). Então ... etc ...
Este é um algoritmo absurdamente simples, mas tenha cuidado ao incluir o item atual na lista ao executar a troca ou quebrará o algoritmo.
A versão de amostragem do reservatório é bem simples:
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
São US $ n linhas selecionadas aleatoriamente do stdin. Substitua o material <>/$ _ por outra coisa se você não estiver usando linhas de um arquivo, mas é um algoritmo bastante direto.
Se a lista for classificada, por exemplo, se você deseja extrair elementos K de n, mas você não se importa com a ordem relativa deles, um algoritmo eficiente é proposto no artigo Um algoritmo eficiente para amostragem aleatória seqüencial (Jeffrey Scott Vitter, Transações ACM em software matemático, Vol. 13, nº 1, março de 1987, páginas 56-67.).
editado Para adicionar o código em C ++ usando o Boost. Acabei de digitar e pode haver muitos erros. Os números aleatórios vêm da biblioteca Boost, com uma semente estúpida, então não faça nada sério com isso.
/* 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
dá o seguinte oupptut no meu laptop
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 rubi mostra o Amostragem de reservatório, algoritmo R método. Em cada ciclo, eu seleciono n=5 inteiros aleatórios únicos de [0,N=10) variar:
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
resultado:
100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034
Todo o número inteiro entre 0-9 foi escolhido com quase a mesma probabilidade.
É essencialmente Algoritmo de Knuth Aplicado a sequências arbitrárias (de fato, essa resposta tem uma versão LISP disso). O algoritmo é SOBRE) com o tempo e pode ser O (1) na memória se a sequência for transmitida para ela como mostrado em @Resposta de Michaelcramer.
Aqui está uma maneira de fazer isso em O (n) sem armazenamento extra. Tenho certeza de que isso não é uma distribuição puramente aleatória, mas provavelmente está perto o suficiente para muitos 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 é o código Perl. Grep é um filtro e, como sempre, não testei esse código.
@list = grep ($_ % I) == 0, (0..N);
- I = intervalo
- N = limite superior
Obtenha apenas números que correspondem ao seu intervalo através do operador do módulo.
@list = grep ($_ % 3) == 0, (0..30);
retornará 0, 3, 6, ... 30
Este é o código Pseudo Perl. Pode ser necessário ajustá -lo para compilar.
