функция воспроизведения в случайном порядке в 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-й бит в двоичном представлении индекса в массиве.

Например, перемещение третьего элемента в массиве является пятым элементом массива. i.e ..

Shuffle (A [010]) = A [100]. (Предполагая размер массива как 8 элементов)

Мы видим, что n-1-й бит '0' оставлен круговым сдвигом. Таким образом, значение A [4] копируется в A [2]. Можем ли мы выполнить это без использования временного массива для всех элементов массива ...

Я хочу реализовать эту функцию в простой простой C, но я просто не мог понять, как изменить бит ...

Предложения пожалуйста ...

Answer 1

Вы можете изменить биты с помощью побитового логических операторов &, | и т.д. Вы можете перемещать биты, используя сдвиг << и >> операторов.

Проще всего это сделать с использованием временного массива, поскольку в противном случае вы можете избежать перезаписи значения, которое вам понадобится позже?

Answer 2

Я не помню, где я нашел этот метод (может быть, «Численные рецепты на C», но я не могу его там нарисовать).

Метод использования bit reversed shuffle (я буду называть его «bitrev» здесь), то сортирует элементы массива, что индекс abcdef элемент становится fedcba (буквы представляют собой биты, 6 бит пример). Три бита возвращается делать свои функции:

1. Используйте два bitrevs на две половины массива, поэтому индекс abcdef становятся afedcb (когда вы действуете на bitrev на половину массива самого высокого индекса бит остается неизменным);

2. Используйте битрев на всей массиве, поэтому индекс afedcb станет bcdefa, и это то, что вам нужно.

Поскольку битрев легко реализуется на месте, это делает вашу работу.

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?

Ниже приведен пример, в C от RosettaCode:

#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); 
}