C++ Academy

🖥 Большинство “простых” shuffle-алгоритмов дают кривой рандом Частая ошибка:

for (int i = 0; i < n; i++) {
    int j = rand() % n;
    swap(a[i], a[j]);
}

На вид всё нормально: каждый элемент случайно меняется местами с другим. Но проблема в вероятностях. Для массива из n элементов существует n! перестановок. Хороший shuffle должен давать каждой перестановке одинаковый шанс. Наивный вариант делает n шагов, и на каждом шаге выбирает индекс из полного диапазона 0..n-1. В итоге некоторые перестановки появляются чаще других. Правильный подход - Fisher-Yates shuffle:

for (int i = n - 1; i > 0; i--) {
    int j = random(0, i);
    swap(a[i], a[j]);
}

Идея простая: на каждом шаге мы выбираем элемент только из ещё не зафиксированной части массива. Сначала выбираем последний элемент из всего массива. Потом предпоследний - из оставшихся. Потом следующий - из ещё меньшего диапазона. Так каждая перестановка получает одинаковую вероятность. В C++ лучше не писать через rand() % n, потому что там может быть ещё и modulo bias. Нормальный вариант:

std::mt19937 rng(std::random_device{}());

for (int i = n - 1; i > 0; --i) {
    std::uniform_int_distribution<int> dist(0, i);
    int j = dist(rng);
    std::swap(a[i], a[j]);
}

Shuffle - хороший пример, где код может выглядеть “рандомным”, но математически быть неправильным.