隨機功能用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); 
}