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

11

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?

Raj Wadhwa
źródło
1
Użyj wektora tablicowego lub bitowego, aby zapisać liczby, które już widzieliśmy, a licznika, aby zapisać liczbę unikalnych liczb.
Dave Clarke
@DaveClarke Jak mogę wygenerować liczbę większą niż 50? Jeśli użyję go więcej niż 1 raz, to w jaki sposób wygeneruję 1, używając ich?
Raj Wadhwa,
1
Wyzwanie oczywiście polega na tym, aby wszystkie miejsca występowały z jednakowym prawdopodobieństwem. Możesz użyć RandNum100 = (RandNum50() * 2) - (RandNum50 > 25) ? 0 : 1).
Dave Clarke
2
@DaveClarke: Więc proponujesz iterowane próbkowanie odrzucenia? To by się zakończyło tylko w oczekiwaniu.
Raphael
Dałem tylko podpowiedź.
Dave Clarke

Odpowiedzi:

3

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 - 1O(N2)krand0k1

 // 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 km=log2(k)rk

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
    }
}
Vor
źródło
1
Strona wikipedii, do której linkujesz, stwierdza, że ​​istnieje wariant . O(n)
Dave Clarke
1
Myślę, że „shuffle” jest tutaj kluczowym hasłem.
Raphael
4
Trik w krand (k) nie daje prawdziwie jednorodnego rozkładu, chociaż jest to dobre przybliżenie: nawet dla k = 3 daje to 33 333 328% szansy na wyjście 0. Czy istnieje uzasadnienie dla sumowania aż do k tutaj ? Sądzę, że mniejszy limit wystarczy, jeśli chcemy tylko przybliżenia.
Erick Wong,
1
@ErickWong: masz rację; Myślę, że prawdziwy równomierny rozkład można osiągnąć tylko przy użyciu metody próbkowania odrzucenia, która nie gwarantuje zakończenia w stałym czasie. Istnieją inne schematy aproksymacji (które pozwalają osiągnąć dowolne aproksymacje), ten, który zaproponowałem, jest pierwszym, który przyszedł mi do głowy.
Vor
2
@ ex0du5: Wiem o tym, ale jak uzyskać jednolitą losową permutację liczb [1..100] przy użyciu tylko jednolitego generatora losowego w [1..100]? Jedyną znaną mi alternatywną metodą jest: krok 1) wybranie losowej wartości w ; step2) jeśli został już wybrany, odrzuć go i przejdź do step1; krok 3) wydrukuj ; step4) jeśli nie wydrukowaliśmy wszystkich 100 liczb, masz krok step1. Ale ta metoda po prostu przesuwa odrzucenie do już wybranych elementów. 1..100 r rr1..100rr
Vor
4

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 .1100!

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 ) 1kRandNum50kkRandNum50kkRandNum50(r1,r2,,rk) c150k ), 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. c1c50kc100!1100!100! k 100 ! 50 tys50kk100!50k

Steven Stadnicki
źródło
2

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):nlogn+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 n1n!123n

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.P50PQ=Pmodnn=100!P>n

Jérémie
źródło
1

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.

Mark Hurd
źródło