C中的随机数组

我正在寻找一个 ANSI C 中的函数,它可以像 PHP 的 shuffle() 那样随机化一个数组。有这样的功能还是我必须自己写?如果我必须自己写,最好/最高效的方法是什么?

到目前为止我的想法:

  • 遍历数组,例如 100 次,并将随机索引与另一个随机索引交换
  • 创建一个新数组并用第一个随机索引填充它,每次检查索引是否已被占用(性能 = 0 复杂性 = 严重)
stack overflow Shuffle array in C
原文答案
author avatar

接受的答案

Asmodiellink 粘贴到 Ben Pfaff's Writings ,用于持久性:

#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 的任何类型( structmemcpy 、...)。对于要运行的示例程序,它需要 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;
}

答案:

作者头像

以下代码确保将基于从 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;
        }
    }
}
作者头像

C 标准中没有随机化数组的函数。

  • 看看 Knuth——他有适合这项工作的算法。
  • 或查看 Bentley - Programming Pearls 或 More Programming Pearls。
  • 或者查看几乎所有算法书籍。

确保公平洗牌(原始顺序的每个排列都有同样的可能性)很简单,但并非微不足道。

作者头像

我将回应 Neil Butterworth 的回答,并指出您第一个想法的一些问题:

你建议,

遍历数组,比如 100 次,然后将一个随机索引与另一个随机索引交换

使这个严谨。我将假设存在 randn(int n) ,它是一些 RNG 的包装器,产生均匀分布在 [0, n-1], and swap(int a[], size_t i, size_t j),

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

which swaps a[i] and a[j]. Now let’s implement your suggestion:

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
}

Notice that this is not any better than this simpler (but still wrong) version:

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

Well, what’s wrong? Consider how many permutations these functions give you: With n (or 2×n for silly_shuffle) random selections in [0, n-1], the code will “fairly” select one of _n_² (or 2×_n_²) ways to shuffle the deck. The trouble is that there are n! = n×(n-1)×⋯×2×1 possible arrangements of the array, and neither _n_² nor 2×_n_² is a multiple of n!, proving that some permutations are more likely than others.

The Fisher-Yates shuffle is actually equivalent to your second suggestion, only with some optimizations that change (performance = 0, complexity = serious) to (performance = very good, complexity = pretty simple). (Actually, I’m not sure that a faster or simpler correct version exists.)

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: See also this post on Coding Horror 中的数字。

作者头像

您正在寻找的函数已经存在于标准 C 库中。它的名字是 qsort 。随机排序可以实现为:

int rand_comparison(const void *a, const void *b)
{
    (void)a; (void)b;

    return rand() % 2 ? +1 : -1;
}

void shuffle(void *base, size_t nmemb, size_t size)
{
    qsort(base, nmemb, size, rand_comparison);
}

这个例子:

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

srand(0); /* each permutation has its number here */

shuffle(arr, 10, sizeof(int));

...输出是:

3, 4, 1, 0, 2, 7, 6, 9, 8, 5
作者头像

这是一个使用 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++] ) );
}
作者头像

我没有在答案中看到它,所以如果它可以帮助任何人,我会提出这个解决方案:

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;
    }
}
作者头像

与 Nomadiq 相同的答案,但 Random 保持简单。如果您一个接一个地调用该函数,则 Random 将是相同的:

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

void shuffle(int aArray[], int cnt){
    int temp, randomNumber;
    time_t t;
    srand((unsigned)time(&t));
    for (int i=cnt-1; i>0; i--) {
        temp = aArray[i];
        randomNumber = (rand() % (i+1));
        aArray[i] = aArray[randomNumber];
        aArray[randomNumber] = temp;
    }
}
作者头像

我看到了答案,我发现了一种简单的方法

#include <stdio.h>
#include <conio.h>
#include <time.h>

int main(void){

    int base[8] = {1,2,3,4,5,6,7,8}, shuffled[8] = {0,0,0,0,0,0,0,0};
    int index, sorted, discart=0;

    srand(time(NULL));
    for(index = 0; index<8; index++){
        discart = 0;
        while(discart==0){
            sorted = rand() % 8;

            if (shuffled[sorted] == 0){
                //This here is just for control of what is happening
                printf("-------------n");
                printf("index: %in sorted: %i n", index,sorted);
                printf("-------------n");

                shuffled[sorted] = base[index];
                discart= 1;
            }
        }
    }

    //This "for" is just to exibe the sequence of items inside your array
    for(index=0;index<8; index++){
        printf("n----n");
        printf("%i", shuffled[index]);
    }

    return 0;
}

请注意,此方法不允许重复项。最后,您可以使用数字和字母,只需将它们替换为字符串即可。

作者头像

此功能将基于随机种子进行洗牌阵列:

void shuffle(int *arr, int size)
{
    srand(time(NULL));

    for (int i = size - 1; i > 0; i--)
    {
        int j = rand() % (i + 1);

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}