C中的随机数组
我正在寻找一个ANSI C中的函数，它将像PHP的shuffle()一样随机化一个数组。 有这样一个function，还是我必须自己写？ 如果我必须自己写，那么最好/最高效的方法是什么？
我的想法到目前为止：
- 比方说迭代100次，然后用另一个随机索引交换一个随机索引
- 创build一个新的数组，并用第一个随机索引来填充，每次检查索引是否已经被使用（performance = 0 complexity = serious）
从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; } } }
编辑 ：这里是一个通用的版本，通过任何types（ int ， struct ，…）通过memcpy 。 通过一个运行的例子程序，它需要VLA，并不是每个编译器都支持这个，所以你可能想把它改成malloc （这会执行的很糟糕）或者一个足够大的静态缓冲区，以适应你抛出的任何types：
#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 。 我已经testing了这个函数的输出，它看起来不错（甚至期望任何数组元素是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 – 他有这个工作的algorithm。
- 或者看看宾利 – 编程珍珠或更多的编程珍珠。
- 或者看几乎任何algorithm书。
确保公平的洗牌（原始订单的每个排列都是相同可能的）是简单的，但不是微不足道的。
这里是一个使用memcpy而不是赋值的解决scheme，因此您可以将其用于任意数据的数组。 你需要两倍的原始数组的内存和成本是线性的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++] ) ); }
我只是回应尼尔·巴特沃斯的回答，并指出你的第一个想法有些麻烦：
你build议，
比方说迭代100次，然后用另一个随机索引交换一个随机索引
做这个严谨。 我假设randn(int n)的存在，一个RNG的包装，产生均匀分布在[0， n -1]中的数字。
void silly_shuffle(size_t n, int a[n]) { for (size_t i = 0; i < n; i++) a[randn(n)] = a[randn(n)]; }
注意，这并不比这个简单的（但仍然是错误的）版本更好：
void bad_shuffle(size_t n, int a[n]) { for (size_t i = 0; i < n; i++) a[i] = a[randn(n)]; }
那么，怎么了？ 考虑这些函数给出了多less个排列：对于[0， n -1]中的n （或者2× n for silly_shuffle ）随机select，代码将“相当”地selectn 2（或2 n 2）个方法之一洗牌。 麻烦的是有n ！ = n ×（ n -1）×…×2×1arrays的可能排列， n 2和n 2都不是n 1的倍数，certificate某些排列比其他排列更可能。
Fisher-Yates shuffle实际上相当于你的第二个build议，只有一些优化改变（performance = 0，complexity = serious）到（performance = very good，complexity = very simple）。 （实际上，我不确定是否存在更快或更简单的正确版本。）
ETA：另见编码恐怖这篇文章 。
