我正在寻找一个 ANSI C 中的函数，它可以像 PHP 的 shuffle() 那样随机化一个数组。有这样的功能还是我必须自己写？如果我必须自己写，最好/最高效的方法是什么？
到目前为止我的想法：
- 遍历数组，例如 100 次，并将随机索引与另一个随机索引交换
- 创建一个新数组并用第一个随机索引填充它，每次检查索引是否已被占用（性能 = 0 复杂性 = 严重）
C中的随机数组
接受的答案
从 Asmodiel 的 link 粘贴到 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 的任何类型（ 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;
}
答案:
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;
}
}
相关问题
-
如何使用特定字符生成特定长度的随机字符数组
-
如何随机化（随机播放）JavaScript 数组？
-
数组中的随机访问
-
随机播放对象的对象或在模板中的 Angular 2 中随机显示元素
-
重复有偏差的随机洗牌会减少偏差吗？
-
char 数组/字符串如何存储在二进制文件中？
-
在 C 中将二维数组归零的最快方法是什么？
-
完美的 shuffle 和 unshuffle，没有辅助数组
-
创建具有随机值的数组
-
如何在Javascript中选择加权随机数组元素？
-
从 JavaScript 数组中获取随机项
-
来自颜色数组的列表视图中每一行的随机颜色
-
为什么以 null 作为回调的 array_map() 会创建一个“数组数组”？
-
如何为批处理文件中文件夹中的每个文件随机生成名称？
-
我有一个整数数组，如何在 mysql 查询（在 php 中）中使用每个整数？
-
Faker老是显示同一张图，如何避免？
-
R中的随机森林（y中的空类和参数长度为0）
-
如何从 Dart 中的列表中获取随机元素？
-
如何在golang中对数组中的字符串进行洗牌？
-
NodeJS Express 中每个请求的全局范围
以下代码确保将基于从 usec 时间获取的随机种子对数组进行洗牌。这也正确地实现了 Fisher–Yates shuffle 。我已经测试了这个函数的输出，它看起来不错（甚至期望任何数组元素都是随机播放后的第一个元素。甚至期望是最后一个元素）。