Памятка по алгоритмам тасования с примерами на Python

9 января 2026

Пусть есть массив из N элементов. Необходимо переставить элементы в случайном порядке. Казалось бы, простейшая задача. Однако первый алгоритм, что приходит на ум, не обязательно является наилучшим.

Для демонстрации я буду использовать Python. В нем есть готовый random.shuffle(). Однако использование кем-то реализованных алгоритмов не приводит к приобретению новых знаний. Такие идиомы языка, как использование range() или синтаксиса a, b = b, a далее я нарушаю сознательно. Воспринимайте написанное, не как программы на Python, а как строгий псевдокод.

Решение, которое первым приходит на ум лично мне, выглядит так:

#!/usr/bin/env python3

from random import random

xs = [1,2,3,4,5]

i = 0
while i < len(xs):
    j = int(random() * len(xs))
    tmp = xs[i]
    xs[i] = xs[j]
    xs[j] = tmp
    i += 1

print(xs)

Для каждого i-го элемента меняем его местами со случайным j-м элементом. Каждый элемент массива переставляется по крайней мере один раз. Значит, будет получена какая-то случайная перестановка. Данное решение я подсмотрел в алгоритме шифрования RC4 еще в школьные годы. Только вместо random() RC4 использует производные значения от ключа шифрования.

Алгоритм решает поставленную задачу, но имеет один недостаток. В предположении, что элементы массива уникальны, алгоритм не обеспечивает равномерное распределение всех возможных перестановок.

Это можно показать следующим образом. В массиве N элементов, и на каждом шаге выбирается один из N элементов для перестановки. Итого, возможно N^N перестановок. Однако существует только N! уникальных перестановок. Поскольку N^N не обязательно делится на N! нацело, то некоторые перестановки более вероятны, чем другие.

Заинтересованным читателям предлагается проверить это экспериментально. Используйте массив xs из 3-х элементов. Вместо случайных j используйте все 3³ = 27 возможных последовательностей: [0,0,0], [0,0,1], и так далее до [2,2,2]. Посчитайте, какие перестановки сколько раз получились.

Для решения проблемы должно быть N! возможных перестановок:

#!/usr/bin/env python3

from random import random

xs = [1,2,3,4,5]

i = 0
while i < len(xs) - 1:
    j = i + int(random() * (len(xs) - i))
    tmp = xs[i]
    xs[i] = xs[j]
    xs[j] = tmp
    i += 1

print(xs)

Здесь мы проходим по всем элементам массива, кроме последнего. На каждом i-м шаге переменная j принимает случайное значение от i до len(xs) - 1. Затем i-й и j-й элементы меняются местами. Таким образом, в начало массива помещается один из N элементов, следом за ним – один из оставшихся N-1 элементов, и так далее. Всего N! возможных перестановок.

Это называется тасованием Фишера-Йетса. Возможны разные его реализации. Например, массив можно обходить не с начала, а с конца.

Тасование можно совместить с инициализацией массива. Вот пример генерации случайной перестановки чисел от 0 до N-1:

#!/usr/bin/env python3

from random import random

# "неинициализированная" память
xs = [-1, -1, -1, -1, -1]

i = 1
xs[0] = 0
while i < len(xs):
    j = int(random() * (i+1))
    if j < i:
        xs[i] = xs[j]
    xs[j] = i
    i += 1

print(xs)

Алгоритм следующий. В начале i-го шага проинициализированы элементы массива с индексами от 0 до i-1. Выбираем случайный элемент с индексом j от 0 до i. Если выбрали уже проинициализированный, то он вытесняется со своей позиции на текущую i-ю позицию. Затем выбранному элементу присваивается значение i.

Это называется алгоритмом Фишера-Йетса наизнанку (inside-out). Как и исходный алгоритм, он дает равномерное распределение возможных перестановок. Примечательно, что алгоритм работает «на лету». То есть, перестановка может генерироваться по мере поступления заранее неизвестных элементов.

Алгоритмы тасования находят применение при написании тех же property-based тестов. Так элементы из max-кучи должны извлекаться в порядке от наибольшего к наименьшему, независимо от того, в каком порядке они добавлялись.