Перемешать массив в C

Ответ 1

Вставка из ссылки Асмодиэля в " Писания Бен Пфаффа" для настойчивости:

#include <stdlib.h>

/* Arrange the N elements of ARRAY in random order.
   Only effective if N is much smaller than RAND_MAX;
   if this may not be the case, use a better random
   number generator. */
void shuffle(int *array, size_t n)
{
    if (n > 1) 
    {
        size_t i;
        for (i = 0; i < n - 1; i++) 
        {
          size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
          int t = array[j];
          array[j] = array[i];
          array[i] = t;
        }
    }
}

EDIT: И здесь общая версия, которая работает для любого типа (int, struct ,...) через memcpy. При использовании примерной программы для нее требуется VLA, а не каждый компилятор поддерживает это, поэтому вы можете изменить это на malloc (который будет работать плохо) или на статический буфер, достаточно большой для размещения любого типа, который вы выбрасываете на него:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* compile and run with
 * cc shuffle.c -o shuffle && ./shuffle */

#define NELEMS(x)  (sizeof(x) / sizeof(x[0]))

/* arrange the N elements of ARRAY in random order.
 * Only effective if N is much smaller than RAND_MAX;
 * if this may not be the case, use a better random
 * number generator. */
static void shuffle(void *array, size_t n, size_t size) {
    char tmp[size];
    char *arr = array;
    size_t stride = size * sizeof(char);

    if (n > 1) {
        size_t i;
        for (i = 0; i < n - 1; ++i) {
            size_t rnd = (size_t) rand();
            size_t j = i + rnd / (RAND_MAX / (n - i) + 1);

            memcpy(tmp, arr + j * stride, size);
            memcpy(arr + j * stride, arr + i * stride, size);
            memcpy(arr + i * stride, tmp, size);
        }
    }
}

#define print_type(count, stmt) \
    do { \
    printf("["); \
    for (size_t i = 0; i < (count); ++i) { \
        stmt; \
    } \
    printf("]\n"); \
    } while (0)

struct cmplex {
    int foo;
    double bar;
};

int main() {
    srand(time(NULL));

    int intarr[] = { 1, -5, 7, 3, 20, 2 };

    print_type(NELEMS(intarr), printf("%d,", intarr[i]));
    shuffle(intarr, NELEMS(intarr), sizeof(intarr[0]));
    print_type(NELEMS(intarr), printf("%d,", intarr[i]));

    struct cmplex cmparr[] = {
        { 1, 3.14 },
        { 5, 7.12 },
        { 9, 8.94 },
        { 20, 1.84 }
    };

    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));
    shuffle(cmparr, NELEMS(cmparr), sizeof(cmparr[0]));
    print_type(NELEMS(intarr), printf("{%d %f},", cmparr[i].foo, cmparr[i].bar));

    return 0;
}

Ответ 2

Следующий код гарантирует, что массив будет перетасован на основе случайного семени, взятого из времени 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;
        }
    }
}

Ответ 3

В стандарте C нет функции для рандомизации массива.

• Посмотрите на Кнута - у него есть алгоритмы для работы.
• Или посмотрите на Bentley - Programming Pearls или More Programming Pearls.
• Или посмотрите практически в любую книгу алгоритмов.

Обеспечение справедливого перемешивания (где каждая перестановка исходного порядка одинаково вероятна) проста, но не является тривиальной.

Ответ 4

Здесь используется решение, которое использует 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++] ) );
}

Ответ 5

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

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

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

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

Перетасовка 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.

Ответ 6

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

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;
    }
}