Ошибка объекта не найдена в пакете прогноза

Я просто отвечу на ответ Нила Баттерворта и укажу на некоторые проблемы с вашей первой мыслью:

Вы предложили

Итерацию через массив, скажем, 100 раз и обмениваться случайным индексом с другим случайным индексом

Сделайте это строгим. Я предполагаю существование randn(int n), обертки вокруг некоторого RNG, создавая числа, равномерно распределенные в [0, n -1] и swap(int a[], size_t i, size_t j),

swap(int a[], size_t i, size_t j) {
  int temp = a[i]; a[i] = a[j]; a[j] = temp;
}

, который меняет местами a[i] и a[j]. Теперь давайте реализуем ваше предложение:

void silly_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, randn(n), randn(n)); // swap two random elements
}

Обратите внимание, что это не лучше этой более простой (но все же неправильной) версии:

void bad_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, randn(n));
}

Что ж, что случилось? Рассмотрим, сколько перестановок эти функции дают вам: с помощью n (или 2 × n для silly_shuffle) случайных выборок в [0, n - 1], код будет «справедливо» выбирать один из вариантов n ² (или 2 × n ²]), чтобы перетасовать колоду. Проблема в том, что есть n ! = n × ( n -1) × ⋯ × 2 × 1 возможных компоновки массива, и ни n ², ни 2 × n ² является кратным n !, доказывая, что некоторые перестановки более вероятны, чем другие.

Shuffle Fisher-Yates на самом деле эквивалентен вашему второму предложению , только с некоторыми изменениями, которые меняются (производительность = 0, сложность = серьезная) до (производительность = очень хорошая, сложность = довольно простая). (На самом деле, я не уверен, что существует более быстрая или более простая версия.)

void fisher_yates_shuffle(size_t n, int a[n]) {
    for (size_t i = 0; i < n; i++)
        swap(a, i, i+randn(n-1-i)); // swap element with random later element
}

ETA: См. Также этот пост в Coding Horror .