C中的随机数组 [英] Shuffle array in C
本文介绍了C中的随机数组的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
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?
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)
解决方案
Pasted from Asmodiel's link to Ben Pfaff's Writings, for persistence:
#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:
#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("]
");
} 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中的随机数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文