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

Question

Я ищу функцию в ANSI C, которая бы рандомизировала массив, как это делает shuffle() в PHP.Есть ли такая функция или я должен написать ее самостоятельно?И если мне придется написать это самостоятельно, каков наилучший / наиболее эффективный способ сделать это?

Мои идеи на данный момент:

• Перебор массива, скажем, 100 раз и обмен случайным индексом с другим случайным индексом
• Создание нового массива изаполнить его случайными индексами из первого, проверяя каждый раз, если индекс уже взят (производительность = 0 сложность = серьезный)

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

РЕДАКТИРОВАНИЕ : А вот универсальная версия, которая работает для любого типа (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;
}

Answer 2

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

Answer 3

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

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

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

Answer 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++] ) );
}

Answer 5

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

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

Перебирайте массив, скажем, 100 рази обмен случайного индекса с другим случайным индексом

Сделайте это строгим.Я предполагаю существование randn(int n), оболочки вокруг некоторого ГСЧ, производящей числа, равномерно распределенные в [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 !, доказывая, что некоторые перестановки более вероятны, чем другие.

Перестановка Фишера-Йейтса фактически эквивалентна вашему второму предложению, только с некоторыми оптимизациями, которыеизменить (производительность = 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 .

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