ograniczenie random.shuffle Pythona

Question

Z Python documentation dla random.shuffle, który bierze listy i losuje kolejność jeśli jego elementy:

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

Czy dotyczy to dowolnego języka, ponieważ ograniczenie wydaje się być zależne od generatora liczb losowych? Czy można napisać funkcję, która może wygenerować dowolną możliwą permutację dowolnej długiej listy?

Answer 1

Zobacz http://mail.python.org/pipermail/python-ideas/2009-March/003670.html. Dokładna długość, od której zaczyna być problemem, zależy od PRNG, ale podstawowy problem zawsze będzie obowiązywał.

Poprzednie pytanie, z którym związany jest @TryPyPy, również koncentruje się na pythonie, ale zaakceptowana odpowiedź wyjaśnia całkiem dobrze, dlaczego tak się zawsze stanie. Parafrazując, można sobie wyobrazić algorytmu naiwnego losowego działa w ten sposób:

1. wygenerować listę, p, wszystkich możliwych permutacji wejścia
2. uzyskać liczbę losową, x, z PRNG
3. The tasuje lista jest p[x]

Jeśli p jest dłuższa niż lista wszystkich możliwych x s PRNG że mogą produkować niektóre permutacji jest nieosiągalny.

Ponieważ fantazyjne algorytmy losowania są w swej istocie sposobem na osiągnięcie tego celu bez konieczności generowania każdej możliwej permutacji przed odrzuceniem wszystkich poza jednym, jedyną możliwością jest uzyskanie prawdziwej losowości.

Answer 2

Tak, jest to możliwe. Możesz napisać generator permutacji, który używa random.SystemRandom dla wszystkich twoich decyzji.

Wadą tego jest to, że twój program może zostać zatrzymany przez dowolnie długi czas, podczas gdy twój system operacyjny gromadzi więcej entropii do użycia.