Алгоритм для генерации N чисел с rand () без дубликатов [duplicate]

Я не видел этого среди ответов, поэтому предлагаю это решение, если оно может помочь кому угодно:

static inline void shuffle(size_t n, int arr[])
{
    size_t      rng;
    size_t      i;
    int         tmp[n];
    int         tmp2[n];

   memcpy(tmp, arr, sizeof(int) * n);
    bzero(tmp2, sizeof(int) * n);
    srand(time(NULL));
    i = 0;
    while (i < n)
    {
        rng = rand() % (n - i);
        while (tmp2[rng] == 1)
            ++rng;
        tmp2[rng] = 1;
        arr[i] = tmp[rng];
        ++i;
    }
}

Здесь решение, которое использует memcpy вместо назначения, поэтому вы можете использовать его для массива по произвольным данным. Вам потребуется в два раза больше памяти исходного массива, а стоимость - линейная O (n):

void main ()
{
    int elesize = sizeof (int);
    int i;
    int r;
    int src [20];
    int tgt [20];

    for (i = 0; i < 20; src [i] = i++);

    srand ( (unsigned int) time (0) );

    for (i = 20; i > 0; i --)
    {
        r = rand () % i;
        memcpy (&tgt [20 - i], &src [r], elesize);
        memcpy (&src [r], &src [i - 1], elesize);
    }
    for (i = 0; i < 20; printf ("%d ", tgt [i++] ) );
}

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

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

Итерацию через массив, скажем, 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 .

Следующий код гарантирует, что массив будет перетасован на основе случайного семени, взятого из времени usec. Также это реализует Fisher-Yates shuffle должным образом. Я тестировал вывод этой функции, и он выглядит хорошо (даже ожидание того, что любой элемент массива является первым элементом после тасования. Также даже ожидание для последнего).

void shuffle(int *array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);


    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}