Перемешать функцию в C - PullRequest
       1

Перемешать функцию в C

1 голос
/ 17 ноября 2010

Функция случайного выбора определяется как

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, но я просто не мог понять, как изменить биты ...

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

Ответы [ 4 ]

1 голос
/ 18 января 2012

Рассматривали ли вы 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);
} 
0 голосов
/ 17 ноября 2010

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

Использование метода бит с обратным перемешиванием (i 'Я назову его «bitrev» здесь), он переупорядочивает элементы массива так, что индекс элемента abcdef становится fedcba (буквы представляют биты, 6-битный пример).Три битовых реверта выполняют ваши функции:

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

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

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

0 голосов
/ 17 ноября 2010

// эта функция имеет сложность 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;
        }
}

Вы можете использовать функцию shuffle с индексом, который является массивом символов, например:

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]);
}
0 голосов
/ 17 ноября 2010

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...