Учитывая конечный набор из N карт, Каков наилучший способ (алгоритм) перетасовать карты, чтобы у меня была лучшая перетасованная карта с минимальными шагами, чтобы получить максимальные случайные перестановки?Каков наилучший алгоритм для перетасовки карт?
Какое оптимальное решение в минимальных шагах?
Это классический (который я считаю, доказуемо самое лучшее, используя точное количество битов, необходимых для Len (х) факторные перестановками):
def shuffle(x):
"""Shuffle list x in place, and return None."""
for i in reversed(range(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]
Выглядит правильно. Важным моментом является то, что вы меняете местами случайное число от i до N, а не от 0 до N, как вы могли бы подумать. Переключение на 0 на N дает странное, неравномерное распределение. –
Использование Fisher Yates algorithm. Многие языки программирования используют вариант этого алгоритма для перетасовки элементов конечного множества. Это псевдо-код Fisher Yates алгоритма (оптимизированной версии Ричарда Durstenfeld):
-- To shuffle an array a of n elements (indices 0..N-1):
for i from N−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
Этот алгоритм обеспечивает равномерное распределение. Для карт N есть N! Возможны перетасованные комбинации. Здесь также может быть возвращена любая из N! перестановок. Сложность времени - O(N).
Как вы определяете '' лучший перетасованный пакет карт''? – Pang
Определите «лучший». Кроме того, этот вопрос либо в основном основан на мнениях, либо запрашивает предложения стороннего контента, оба из которых неактуальны здесь, в Stack Overflow. –
минимальные шаги и расстояния между картами, очевидно, некоторые виды перетасовки превосходят другие. –