Algoritmo mais eficiente para imprimir 1-100 usando um determinado gerador de números aleatórios

Nos é dado um gerador de números aleatórios RandNum50que gera um número inteiro aleatório uniformemente no intervalo de 1 a 50. Podemos usar apenas esse gerador de números aleatórios para gerar e imprimir todos os números inteiros de 1 a 100 em uma ordem aleatória. Todo número deve vir exatamente uma vez, e a probabilidade de qualquer número ocorrer em qualquer lugar deve ser igual.

Qual é o algoritmo mais eficiente para isso?

Pensei (para que possa estar errado :-) nesta solução que usa o shuffle de Fisher-Yates . Para manter uma distribuição uniforme com boa aproximação (consulte a seção EDIT abaixo) a cada iteração, você pode usar este truque para produzir um valor entre e :0 k - $O(N^2)$krand$0$$k-1$

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {    
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

O algoritmo de Fisher-Yates se torna:

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

EDITAR:

Como apontado por Erick, a krandfunção acima não retorna uma distribuição verdadeiramente uniforme. Existem outros métodos que podem ser usados ​​para obter uma aproximação melhor (arbitrariamente melhor) e mais rápida; mas (até onde ), a única maneira de obter uma distribuição verdadeiramente uniforme é usar a amostragem por rejeição : escolha bits aleatórios e se o número obtido for menor que devolva-o, caso contrário, gere outro número aleatório; uma possível implementação:r $m = \lceil \log_2(k) \rceil$$r$$k$

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits        
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }      
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

Como outras pessoas deram soluções aproximadas e envolvem a obtenção de números indeterminados de desvios, que tal uma prova de que não existe tal algoritmo que garanta apenas um número finito de RandNum50()chamadas?

Como outros observaram, imprimir os números de 1 a 100 em ordem aleatória é equivalente a imprimir uma permutação aleatória desses números; existem 100! dessas permutações e, portanto, qualquer permutação específica deve ser gerada com probabilidade .$\frac{1}{100!}$

Mas se soubéssemos que nosso algoritmo usava no máximo chamadas para alguns , poderíamos argumentar da seguinte maneira: primeiro, cubra os caminhos de computação que fazem menos de chamadas para fazer chamadas fictícias adicionais (ou seja, chamadas onde o valor retornado é irrelevante), de modo que todos os caminhos de computação fazem exatamente chamadas. Qualquer sequência de resultante de nossas chamadas para deve resultar em alguma permutação de saída e, portanto, podemos criar uma 'tabela de resultados' que mapeia qualquer sequência de resultados de nossas chamadas em um determinado permutação de saída. Como cada um desses resultados é igualmente provável (cada um deles tem probabilidadek k k k ( r 1 , r 2 , … , r k ) $k$RandNum50$k$$k$RandNum50$k$$k$RandNum50$(r_1, r_2, \ldots, r_k)$$\displaystyle\frac{1}{50^k}$ ), então a probabilidade de obter qualquer permutação específica de nosso algoritmo deve estar no formato para alguns . Mas Não pode ser desta forma, porquenão divide por nenhum (por exemplo, 3 divide mas não pode dividir nenhum número da forma ). Isso significa que nenhuma distribuição possível de resultados para chamadas com números aleatórios pode produzir uma permutação uniforme. c$\displaystyle\frac{c}{50^k}$$c$100! 50k$\displaystyle\frac{1}{100!}$$100!$$50^k$$k$50 $100!$$50^k$

As soluções anteriores não são ótimas. A complexidade é exatamente nas chamadas para RandNum50 e é descrita em alguns detalhes aqui , usando como fonte de bit aleatório (como sugerido por Vor):$n\log n + O(1)$

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

A idéia básica é que você salve muitos bits se gerar um uniforme entre e, E, em seguida, utilizando a decomposição de base fatorial , em vez de gerar uma sequência de uniformes variou-se a , em seguida, , então , etc., . Este é realmente, como mencionei no post, o tópico de um artigo que enviei!n ! 1 2 3 $1$$n!$$1$$2$$3$$n$

Se você não souber como gerar um uniforme, como sugerido nesse post, a partir de um bit aleatório, também poderá gerar uma aproximação do uniforme diretamente, desta maneira (o que é equivalente ao "trulyrand" de Vor, mas mais rápido):

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

indo o mais longe que você precisa. Isso está desenvolvendo na base . Em seguida, basta truncar , ou seja, , no seu caso. Esse valor não é completamente aleatório, mas é uma medida de uniformidade que é frequentemente usada. Ou, como Vor sugere, você pode rejeitar se . Então, com esse valor, você pode fazer a expansão da base fatorial, conforme descrito na publicação .50 $P$$50$$P$n = 100 ! P > $Q=P\mod n$$n=100!$$P>n$

Eu não fiz a análise para confirmar o quão uniforme (ou não) isso seria, e poderia ser ajustado para ser um verdadeiro embaralhamento, mas você poderia escolher, a partir de uma matriz inicial do ith index = i + 1, o (k + RandNum50() + RandNum50() - 1) mod (100 - k)índice, com remoção, para k= 0..99?

Isso "empurra" o pico da RandNum50() + RandNum50()distribuição adiante uniformemente.

_{Tenho certeza de que isso não está certo, como afirmei, porque o índice 0 (1) não pode ser obtido desde a primeira escolha e não consigo ver rapidamente um ajuste alternativo 1..50 + 1..50 que produz 0 ..99.}

Atualizar

Para corrigir o problema que observei, usei efetivamente RandNum100conforme mencionado nos comentários da pergunta para inicializar aleatoriamente o primeiro kdeslocamento.

Isso produz uma distribuição com uma onda significativa na frente.

Em vez de avançar 1, usei outro RandNum50para incrementar isso primeiro k. Isso produz um resultado que é aleatório o suficiente para mim, mas ainda não é "verdadeiramente" aleatório, como pode ser facilmente visto se você alterar K para 2.

Testando o código VB.NET, onde eu atendi qualquer K. par. Note que é O (K), 6K + 2, de fato.