随机功能用C

Question

甲随机播放功能被定义为

Shuffle(A[n-1],A[n-2].....A[1],A[0]) = A[n-2]A[n-3]......A[1],A[0],A[n-1] 

，其中i在A [i]于代表的I个比特在所述阵列中的索引的二进制表示。

例如，数组中的第三个元素的shuffle是第五个数组元素。即...

随机播放（A [010]）= A [100]。 （假设数组大小为8个元素）

我们看到第n-1位'0'是左循环移位。所以A [4]的值被复制到A [2]中。我们可以执行这个不使用临时数组的数组中的所有元素...

我想实现简单的纯C这个功能，但我只是不知道如何改变位...

建议请...

Answer 1

您可以使用位逻辑运算符&更改位，|等。您可以使用shift <<和>>运营商移动位。

使用临时数组来完成这个操作最简单，否则您将如何避免覆盖稍后需要的值？

Answer 2

我不记得我在哪里找到这种方法（可能是“C中的数值食谱”，但我无法在那里找到它）。

使用方法bit reversed shuffle（我将它命名为“bitrev”），它重新排列元素索引abcdef变为fedcba（字母表示位，6位示例）的数组元素。三位恢复做你的功能：

1. 使用两个bitrevs到阵列的两半，所以指数abcdef成为afedcb（当你采取行动bitrev在阵列指数最高位的一半保持不变）;

2. 整个阵列使用bitrev，所以索引afedcb变成bcdefa，这就是你需要的。

由于bitrev很容易在本地实施，因此您可以进行这项工作。

Answer 3

//此函数具有复杂度O（N）

void shuffle(char *p, unsigned int pSize) 
{ 
     unsigned int i = 0; 
     for(i=0 ; i < (pSize - 1); i++) 
     { 
     char lTmpChar=p[i]; 
     p[i]=p[i+1]; 
     p[i+1]=lTmpChar; 
     } 
} 

或使用模板（C++）：

template <typename T> void shuffle(T *p, unsigned int pSize) 
{ 
     unsigned int i = 0; 
     for(i=0 ; i < (pSize - 1); i++) 
     { 
     T lTmpChar=p[i]; 
     p[i]=p[i+1]; 
     p[i+1]=lTmpChar; 
     } 
} 

您可以使用随机播放功能与作为字符数组的索引，例如：

int arraySize = 10; 
char array[arraySize]='abcdefghil'; 
char index[4]='0010'; 
int shuffled_index = atoi(shuffle(index,4)); 
if(shuffled_index < arraySize) // note that shuffled_index is not always valid 
{ 
printf("Char: %c", array[shuffled_index]); 
} 

Answer 4

您是否考虑过Knuth Shuffle？

下面是从RosettaCode C中的例子：

#include <stdlib.h> 
#include <string.h> 

int rrand(int m) 
{ 
    return (int)((double)m * (rand()/(RAND_MAX+1.0))); 
} 

#define BYTE(X) ((unsigned char *)(X)) 
void shuffle(void *obj, size_t nmemb, size_t size) 
{ 
    void *temp = malloc(size); 
    size_t n = nmemb; 
    while (n > 1) { 
    size_t k = rrand(n--); 
    memcpy(temp, BYTE(obj) + n*size, size); 
    memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size); 
    memcpy(BYTE(obj) + k*size, temp, size); 
    } 
    free(temp); 
}