Maksymalna długość listy do przetasowania z random.shuffle w Pythonie?

Question

Mam listę którą shuffle Python zbudowany w funkcję losowego (random.shuffle)

Jednak państw referencyjnych Pythona:

pamiętać, że nawet niewielkim len(x), całkowita liczba permutacji x jest większy niż okres większości generatorów liczb losowych; oznacza to, że większość permutacji długiej sekwencji nigdy nie zostanie wygenerowana.

Teraz zastanawiam się, co to znaczy "raczej mały len (x)". 100, 1000, 10000, ...

Answer 1

TL; DR: It „przerwy” na listach z ponad 2080 elementów, ale nie przejmuj się zbytnio :)

pełna odpowiedź:

Przede wszystkim należy zauważyć, że „tasowania” listę może być rozumiane (konceptualnie) jako generowanie wszystkich możliwych permutacji elementów list i wybieranie jednej z tych permutacji losowo.

Następnie należy pamiętać, że wszystkie samodzielne skomputeryzowane generatory liczb losowych są w rzeczywistości "pseudo" losowe. Oznacza to, że w rzeczywistości nie są przypadkowe, ale polegają na szeregu czynników, które próbują wygenerować liczbę trudną do odgadnięcia w sposób zaawansowany lub celowo odtworzony. Wśród tych czynników jest zwykle poprzednia wygenerowana liczba. Tak więc w praktyce, jeśli użyjesz losowego generatora w sposób ciągły określoną liczbę razy, w końcu zaczniesz ponownie otrzymywać tę samą sekwencję (jest to "okres", do którego odnosi się dokumentacja).

Wreszcie, docstring na Lib/random.py (moduł losowy) mówi, że "Okres [generatora liczb losowych] to 2**19937-1."

W związku z tym, jeśli lista jest taka, że ​​istnieje 2**19937 lub więcej kombinacji, niektóre z nich nigdy nie zostaną uzyskane przez przetasowanie listy. Powinieneś (ponownie, koncepcyjnie) wygenerować wszystkie permutacje listy, następnie wygenerować losową liczbę x i wybrać permutację x. Następnym razem wygenerujesz kolejną losową liczbę y i wybierzesz Y. permutację. I tak dalej. Ale ponieważ istnieje więcej permutacji, niż dostaniesz losowe liczby (ponieważ, co najwyżej po 2**19937-1 wygenerowanych liczbach, zaczniesz znowu otrzymywać te same), zaczniesz znowu wybierać te same permutacje.

Jak widzisz, nie jest to kwestia długości twojej listy (chociaż to wchodzi w równanie). Ponadto, 2**19937-1 jest dość długa. Ale nadal, w zależności od twoich tasujących potrzeb, powinieneś o tym pamiętać. W uproszczonym przypadku (iz szybkim obliczeniem), dla listy bez powtarzających się elementów, 2081 elementów dałoby permutację 2081!, która jest większa niż 2**19937.

Answer 2

To, co mają na myśli to to, że permutacje na n obiektach (oznaczone n!) Rosną bardzo szybko w absurdalny sposób.

Zasadniczo n! = n x n-1 x ... x 1; na przykład 5! = 5 x 4 x 3 x 2 x 1 = 120, co oznacza, że ​​istnieje 120 możliwych sposobów tasowania listy 5 elementów.

Na tej samej dokumentacji strony Python podają 2^19937-1 jako okres, który wynosi 4. coś około 10^6001 lub coś podobnego. Opierając się na stronie Wikipedii na silni, myślę, że 2000! powinno być wokół tego. (Niestety, nie znalazłem dokładnej liczby).

W zasadzie istnieje tak wiele możliwych permutacji, że shuffle odejdzie od tego, że prawdopodobnie nie ma prawdziwego powodu, by martwić się o tych, których nie będzie.

Ale jeśli to naprawdę problem (brzydki klient prosi o gwarancję losowości, być może?), Można również odładować to zadanie do innej firmy; patrz na przykład http://www.random.org/.

Answer 3

pisałem, że komentarz w źródle Python pierwotnie, więc może uda mi się wyjaśnić ;-)

Gdy Komentarz został wprowadzony, generator Pythona Wichmann-Hill miał znacznie krótszy okres, a my nie możemy nawet generować wszystkie permutacje talii kart.

Okres jest teraz astronomicznie większy, a 2080 jest prawidłowy dla aktualnej górnej granicy. Dokumenty można by poprawić, by powiedzieć więcej na ten temat - ale stałyby się strasznie nudne.

Istnieje bardzo proste wyjaśnienie: PRNG okresu P ma możliwe stany początkowe. Stan początkowy w pełni determinuje wytworzoną permutację. Dlatego PRNG z okresu P nie może wygenerować więcej niż P odrębnych permutacji (a to absolutne górne ograniczenie - może nie zostać osiągnięte). Dlatego porównując N! na P jest poprawne obliczenie tutaj. I rzeczywiście:

>>> math.factorial(2080) > 2**19937 - 1 
False 
>>> math.factorial(2081) > 2**19937 - 1 
True