C语言 C 中的随机数组

Shuffle array in C

提问by Asmodiel

I'm looking for a function in ANSI C that would randomize an array just like PHP's shuffle()does. Is there such a function or do I have to write it on my own? And if I have to write it on my own, what's the best/most performant way to do it?

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

My ideas so far:

到目前为止我的想法：

• Iterate through the array for, say, 100 times and exchange a random index with another random index
• Create a new array and fill it with random indices from the first one checking each time if the index is already taken (performance = 0 complexity = serious)

• 遍历数组，例如 100 次，然后将一个随机索引与另一个随机索引交换
• 创建一个新数组并用第一个数组中的随机索引填充它，每次检查是否已经使用了索引（性能 = 0 复杂性 = 严重）

回答by John Leehey

Pasted from Asmodiel's linkto Ben Pfaff's Writings, for persistence:

从Asmodiel的链接粘贴到Ben Pfaff 的著作，为了持久性：

#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: And here's a generic version that works for any type (int, struct, ...) through memcpy. With an example program to run, it requires VLAs, not every compiler supports this so you might want to change that to malloc(which will perform badly) or a static buffer large enough to accommodate any type you throw at it:

编辑：这是一个通用版本，适用于任何类型 ( 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;
}

回答by Nomadiq

The following code ensures that the array will be shuffled based on a random seed taken from the usec time. Also this implements the Fisher–Yates shuffleproperly. I've tested the output of this function and it looks good (even expectation of any array element being the first element after shuffle. Also even expectation for being the last).

以下代码确保将根据从 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;
        }
    }
}

回答by Jonathan Leffler

There isn't a function in the C standard to randomize an array.

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

• Look at Knuth - he has algorithms for the job.
• Or look at Bentley - Programming Pearls or More Programming Pearls.
• Or look in almost any algorithms book.

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

Ensuring a fair shuffle (where every permutation of the original order is equally likely) is simple, but not trivial.

确保公平洗牌（原始顺序的每个排列的可能性相同）很简单，但并非微不足道。

回答by Hyperboreus

Here a solution that uses memcpy instead of assignment, so you can use it for array over arbitrary data. You need twice the memory of original array and the cost is linear O(n):

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

回答by J. C. Salomon

I'll just echo Neil Butterworth's answer, and point out some trouble with your first idea:

我只会回应尼尔巴特沃斯的回答，并指出你的第一个想法的一些问题：

You suggested,

你建议，

Iterate through the array for, say, 100 times and exchange a random index with another random index

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

Make this rigorous. I'll assume the existence of randn(int n), a wrapper around some RNG, producing numbers evenly distributed in [0, n-1], and swap(int a[], size_t i, size_t j),

做这个严谨。我将假设存在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;
}

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

其中交换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
}

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×nfor silly_shuffle) random selections in [0, n-1], the code will “fairly” select one of n2 (or 2×n2) ways to shuffle the deck. The trouble is that there are n! = n×(n-1)×?×2×1 possible arrangements of the array, and neither n2 nor 2×n2 is a multiple of n!, proving that some permutations are more likely than others.

嗯，怎么了？考虑这些函数给你多少排列：在 [0, n-1] 中有n（或 2× nfor silly_shuffle）个随机选择，代码将“公平地”选择n2（或 2× n2）种方式中的一种进行洗牌甲板。问题是有n！= n×( n-1)×?×2×1 个可能的排列排列，并且n2 和 2× n2 都不是n!的倍数，证明某些排列比其他排列更有可能。

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.)

Fisher-Yates shuffle 实际上等同于您的第二个建议，只是进行了一些优化，将（性能 = 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: See also this post on Coding Horror.

ETA：另请参阅Coding Horror 上的这篇文章。

回答by DaBler

The function you are looking for is already present in the standard C library. Its name is qsort. Random sorting can be implemented as:

您正在寻找的函数已经存在于标准 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);
}

The example:

这个例子：

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

...and the output is:

...输出是：

3, 4, 1, 0, 2, 7, 6, 9, 8, 5

回答by Antonin GAVREL

I didn't see it among answers so I propose this solution if it can help anybody:

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

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