Максимальная Длина Списка для Перестановки с Python random.shuffle?
У меня есть список, который я переставляю с Python, созданным в функции перестановки (random.shuffle)
Однако ссылочные состояния Python:
Отметьте это даже довольно маленьким
len(x), общее количество перестановок x больше, чем период наиболее генераторов случайных чисел; это подразумевает, что большинство перестановок длинной последовательности никогда не может быть сгенерировано.
Теперь, интересно, что означает этот "довольно маленький len (x)". 100, 1000, 10000...
2 ответа
TL; DR: Он "ломается" в списках с более чем 2080 элементами, но не беспокойтесь слишком сильно :)
Полный ответ:
Прежде всего, обратите внимание, что " «перетасовка» списка может пониматься (концептуально) как генерирование всех возможных перестановок элементов списков и случайный выбор одной из этих перестановок.
Тогда вы должны помнить, что все автономные компьютеризированные генераторы случайных чисел на самом деле являются «псевдослучайными». То есть они на самом деле не случайны, а зависят от ряда факторов, чтобы попытаться получить число, которое трудно угадать заранее или целенаправленно воспроизвести. Среди этих факторов обычно есть предыдущее сгенерированное число. Итак, на практике, если вы используете случайный генератор непрерывно определенное количество раз, вы в конечном итоге начнете получать одну и ту же последовательность снова и снова (это «период», на который ссылается документация).
Наконец, в строке документации Lib / random.py (модуль random) указано, что «Период [генератора случайных чисел] равен 2 ** 19937-1 ».
Итак, учитывая все это, если ваш список таков, что есть 2 ** 19937 или более перестановок, некоторые из них никогда не будут получены путем перетасовки списка. Вы (опять же, концептуально) сгенерируете все перестановки списка, затем сгенерируете случайное число x и выберете x-ю перестановку. В следующий раз вы создадите другое случайное число y и выберете y-ю перестановку. И так далее.Но поскольку существует больше перестановок, чем вы получите случайных чисел (поскольку самое большее после 2 ** 19937-1 сгенерированных чисел вы снова начнете получать те же самые числа), вы начнете снова выбирая те же самые перестановки.
Итак, видите ли, дело не в том, как долго ваш список (хотя это входит в уравнение). Кроме того, 2 ** 19937-1 - довольно длинное число. Но все же, в зависимости от ваших потребностей в перетасовке, вы должны все это иметь в виду. В упрощенном случае (и с быстрым вычислением) для списка без повторяющихся элементов 2081 элемент даст 2081! перестановок, что больше, чем 2 ** 19937 .
Они означают, что количество перестановок на n объектах (отмеченных n!) Очень быстро растет до абсурдно высокого уровня.
В основном n! знак равно n x n-1 x ... x 1; например, 5! = 5 x 4 x 3 x 2 x 1 = 120, что означает, что существует 120 возможных способов перетасовки списка из 5 пунктов.
В документации на той же странице Python в качестве точки указывается 2 ^ 19937-1, что равно 4 чем-то × 10 ^ 6001 или что-то в этом роде. Судя по странице факториалов в Википедии, я думаю, 2000! должно быть примерно так. (Извините, я не нашел точной цифры.)
Так что в принципе существует так много возможных перестановок, из которых будет происходить перемешивание, что, вероятно, нет реальной причины беспокоиться о тех, которые не будут.
Но если это действительно проблема (надоедливый клиент, возможно, просит гарантии случайности?), Вы также можете передать задачу какой-нибудь третьей стороне; см., например, http://www.random.org/ .