C中的随机数组

Question

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

我的想法到目前为止:

• 例如,遍历数组100次,并将随机索引与另一个随机索引交换
• 创建一个新数组并用第一个随机索引填充它,每次检查索引是否已被采用(性能= 0复杂度=严重)

Answer 1

从粘贴Asmodiel的链接到本普法夫的著作,持久性:

#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

以下代码确保基于从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;
        }
    }
}

Answer 3

I\xe2\x80\x99ll 只是回应 Neil Butterworth\xe2\x80\x99s 的答案，并指出你的第一个想法的一些问题：

\n

你建议，

\n

\n

迭代数组，例如 100 次，并将一个随机索引与另一个随机索引交换

\n

\n

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

\n

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

\n

交换a[i]和a[j]。\n现在让\xe2\x80\x99s 实现你的建议：

\n

void silly_shuffle(size_t n, int a[n]) {\n    for (size_t i = 0; i < n; i++)\n        swap(a, randn(n), randn(n)); // swap two random elements\n}\n

\n

请注意，这并不比这个更简单（但仍然错误）的版本更好：

\n

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

\n

嗯，什么\xe2\x80\x99s 错了？考虑一下这些函数为您提供了多少种排列：在 [0, n -1] 中随机选择n（或 2\xc3\x97_n_ ） ，代码将 \xe2\x80\x9cfairly\xe2\x80\x9d 选择 _n_ 之一\xc2\xb2 （或 2\xc3\x97_n_\xc2\xb2）种洗牌方式。问题是有n个！= _n_\xc3\x97( n -1)\xc3\x97\xe2\x8b\xaf\xc3\x972\xc3\x971 可能的数组排列，并且既不是 _n_\xc2\xb2 也不是 2\xc3\x97_n_\xc2 \xb2 是n !的倍数，证明某些排列比其他排列更有可能。silly_shuffle

\n

Fisher-Yates shuffle 实际上相当于您的第二个建议，只是进行了一些优化，将（性能 = 0，复杂性 = 严重）更改为（性能 = 非常好，复杂性 = 非常简单）。（实际上，我\xe2\x80\x99m不确定是否存在更快或更简单的正确版本。）

\n

void fisher_yates_shuffle(size_t n, int a[n]) {\n    for (size_t i = 0; i < n; i++)\n        swap(a, i, i+randn(n-1-i)); // swap element with random later element\n}\n

\n

ETA：另请参阅这篇有关编码恐怖的文章。

\n

Answer 4

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

• 看看Knuth--他有工作的算法.
• 或者看看Bentley - Programming Pearls或More Programming Pearls.
• 或者查看几乎所有的算法书.

确保公平的洗牌(原始订单的每个排列同样可能)是简单的,但不是微不足道的.

Answer 5

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