Najbardziej wydajny algorytm do drukowania 1-100 przy użyciu danego generatora liczb losowych

Dostajemy generator liczb losowych, RandNum50który generuje losową liczbę całkowitą równomiernie w zakresie 1–50. Możemy używać tylko tego generatora liczb losowych do generowania i drukowania wszystkich liczb całkowitych od 1 do 100 w losowej kolejności. Każda liczba musi przyjść dokładnie raz, a prawdopodobieństwo wystąpienia dowolnej liczby w dowolnym miejscu musi być równe.

Jaki jest najbardziej wydajny algorytm?

Pomyślałem (więc może być źle :-) o tym rozwiązaniu , które wykorzystuje losowanie Fisher-Yates . Aby zachować równomierny rozkład z dobrym przybliżeniem (patrz sekcja EDYCJA poniżej) przy każdej iteracji, możesz użyć tej sztuczki, aby uzyskać wartość między a :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
 }

Algorytm Fisher-Yates staje się:

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]

EDYTOWAĆ:

Jak wskazał Erick, krandpowyższa funkcja nie zwraca naprawdę jednorodnego rozkładu. Istnieją inne metody, które można zastosować, aby uzyskać lepsze (arbitralnie lepsze) i szybsze zbliżenie; ale (o ile mi wiadomo) jedynym sposobem na uzyskanie naprawdę jednolitego rozkładu jest użycie próbkowania odrzucającego : wybierz losowych bitów i jeśli uzyskana liczba jest mniejsza niż zwróć ją, w przeciwnym razie wygeneruj inną liczbę losową; możliwe wdrożenie: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
    }
}

Skoro inni ludzie podali przybliżone rozwiązania i rozwiązania polegające na przyjmowaniu nieokreślonej liczby odchyleń, to co powiesz na dowód, że nie ma takiego algorytmu, który gwarantowałby tylko skończoną liczbę RandNum50()połączeń?

Jak zauważyli inni, drukowanie liczb od 1 do 100 w losowej kolejności jest równoważne drukowaniu losowej permutacji tych liczb; jest ich 100! tych permutacji, więc każda konkretna permutacja musi być wyprowadzona z prawdopodobieństwem .$\frac{1}{100!}$

Ale gdybyśmy wiedzieli, że nasz algorytm użył co najwyżej wywołań dla niektórych , moglibyśmy argumentować w następujący sposób: po pierwsze, wypisz ścieżki obliczeniowe, które wykonują mniej niż wywołań, aby wykonać dodatkowe wywołania pozorne (tj. zwracana wartość nie ma znaczenia), dlatego wszystkie ścieżki obliczeniowe wykonują dokładnie wywołań. Dana sekwencja wyników z naszych wywołań musi skutkować pewną permutacją wyjściową, dlatego możemy zbudować „tabelę wyników”, która odwzorowuje dowolną sekwencję wyników z naszych wywołań na określony permutacja wyjściowa. Ponieważ każdy z tych wyników jest jednakowo prawdopodobny (każdy z nich ma prawdopodobieństwok 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}$ ), wówczas prawdopodobieństwo uzyskania określonej permutacji z naszego algorytmu musi mieć postać dla niektórych . Ale Nie może mieć takiej postaci, ponieważnie dzieli dla żadnego (na przykład 3 dzieli ale nie może podzielić żadnej liczby ). Oznacza to, że żaden możliwy rozkład wyników na połączenia z numerami losowymi nie może zapewnić jednolitej permutacji. c$\displaystyle\frac{c}{50^k}$$c$100$\displaystyle\frac{1}{100!}$$100!$ k 100 ! 50 $50^k$$k$$100!$$50^k$

Poprzednie rozwiązania nie są optymalne. Złożoność jest dokładnie w wywołań RandNum50 i jest opisany bardziej szczegółowo tutaj , wykorzystując jako źródło losowych bitów (jako sugerowane przez VOR):$n\log n + O(1)$

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

Podstawową ideą jest to, że oszczędzasz dużo bitów, jeśli wygenerujesz jednolity od do, a następnie stosując rozkład czynnikowy zasad , zamiast generować sekwencję mundurów w zakresie do , następnie , a następnie itd., . To jest, jak wspomniałem w poście, temat artykułu, który przesłałem!n ! 1 2 3 $1$$n!$$1$$2$$3$$n$

Jeśli nie wiesz, jak wygenerować mundur, jak zasugerowano w tym poście, z losowego bitu, możesz również wygenerować przybliżenie munduru bezpośrednio w ten sposób (co odpowiada „trulyrandowi” Vora, ale szybciej):

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

idąc tak daleko, jak trzeba. Rozwija się w bazie . Następnie po prostu skróć , tj. , w twoim przypadku. Ta wartość nie jest całkowicie losowa, ale często stosuje się miarę jednolitości. Lub, jak sugeruje Vor, możesz odrzucić, jeśli . Następnie za pomocą tej wartości można dokonać silnego rozszerzenia bazy, jak opisano w poście .50 $P$$50$$P$$Q=P\mod n$$n=100!$$P>n$

Nie zrobiłem analizę, aby potwierdzić jak jednolita (lub nie) to będzie, a to może być dostosowane do być prawdziwym shuffle, ale można po prostu wybrać, począwszy od tablicy o iindeksie = th i + 1, ten (k + RandNum50() + RandNum50() - 1) mod (100 - k)indeks, z usunięcie, dla k= 0..99?

To „popycha” szczyt RandNum50() + RandNum50()rozkładu równomiernie do przodu.

_{Jestem całkiem pewien, że to nie do końca tak, jak to stwierdziłem, ponieważ indeksu 0 (1) nie można uzyskać od pierwszego wyboru i nie mogę szybko zobaczyć alternatywnej korekty 1..50 + 1..50, która daje 0 ..99.}

Aktualizacja

Aby rozwiązać problem, który zauważyłem, skutecznie użyłem, RandNum100jak wspomniano w komentarzach do pytania, aby losowo zainicjować pierwsze kprzesunięcie.

Daje to rozkład ze znaczną falą z przodu.

Zamiast awansować o 1, użyłem innego, RandNum50aby zwiększyć to pierwsze k. Daje to wynik, który jest dla mnie wystarczająco losowy, ale nadal nie jest „prawdziwie” losowy, co można łatwo zobaczyć, jeśli zmienisz K na 2.

Testowanie kodu VB.NET, w którym spełniałem kryteria dla dowolnego parzystego K. Uwaga: w rzeczywistości jest to O (K), 6K + 2.