Тасование Фишера–Йетса
Каждая перестановка равновероятна за один проход — и один seed всегда даёт одно перемешивание.
1function shuffle<T>(a: T[], seed: number): T[] {2 const rng = createRandom(seed)3 for (let i = a.length - 1; i > 0; i--) {4 const j = Math.floor(rng() * (i + 1))5 swap(a, i, j)6 }7 return a8}Проблема
Перемешать массив честно: так, чтобы каждая из n! перестановок выпадала с равной вероятностью. Наивный «swap со случайным» даёт перекос — некоторые порядки вероятнее.
Что вы видите
Столбики: i идёт с конца, случайный j из ещё не перемешанных, обмен — и позиция i зафиксирована навсегда. Seed генератора определяет всю последовательность обменов.
Как это работает
На шаге i выбираем j равномерно из 0..i: ровно i+1 исходов, каждый одинаково вероятен — отсюда честность. Детерминизм: один seed → одна перестановка, что и делает возможными воспроизводимые демо и ролики.
Пошаговый разбор
- 01
Выбор j
Равномерно из ещё не перемешанных 0..i.
- 02
Обмен
a[i] ↔ a[j].
- 03
Фиксация
Позиция i готова, назад не тянем.
- 04
Повторяемость
Тот же seed — то же перемешивание.
Complexity и ограничения
O(n), память O(1). Требование — честный ГПСЧ с seed.
Edge cases
- Наивный shuffle
Перекос вероятностей — некоторые порядки чаще.
- Слабый ГПСЧ
«Случайность» предсказуема.
- n = 1
Обменов нет.
Где встречается в реальности
Демо-данные
Воспроизводимые перемешивания тестов и визуализаций.
Игры
Тасование колод — канонический пример.
A/B-тесты
Случайное распределение по группам с фиксацией seed.
Связанные алгоритмы
«Одно перемешивание — один seed. Почему это честно»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.