🖥 Большинство “простых” 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 - хороший пример, где код может выглядеть “рандомным”, но математически быть неправильным.