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