Dostajemy generator liczb losowych, RandNum50
któ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?
algorithms
integers
randomness
random-number-generator
Raj Wadhwa
źródło
źródło
RandNum100 = (RandNum50() * 2) - (RandNum50 > 25) ? 0 : 1)
.Odpowiedzi:
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) 0 k−1
krand
Algorytm Fisher-Yates staje się:
EDYTOWAĆ:
Jak wskazał Erick,m=⌈log2(k)⌉ r k
krand
powyż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 kźródło
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 ) 1k k k k k (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. c1c50k c 100!1100! 100! k 100 ! 50 tys50k k 100! 50k
RandNum50
RandNum50
RandNum50
źródło
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)
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 n1 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):
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.P 50 P Q=Pmodn n=100! P>n
źródło
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
i
indeksie = thi + 1
, ten(k + RandNum50() + RandNum50() - 1) mod (100 - k)
indeks, z usunięcie, dlak
= 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,
RandNum100
jak wspomniano w komentarzach do pytania, aby losowo zainicjować pierwszek
przesunięcie.Daje to rozkład ze znaczną falą z przodu.
Zamiast awansować o 1, użyłem innego,
RandNum50
aby zwiększyć to pierwszek
. 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.
źródło