Shuffle function in C

A shuffle function is defined as

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

where i in A[i] represent the I th bit in开发者_如何学Python the binary representation of the index in the array . The

For example , the shuffle of the third element in an array is fifth array element. i.e..

Shuffle(A[010]) = A[100]. (Assuming the array size as 8 elements)

We see that the n-1 th bit '0' is left circular shifted . So the value of A[4] is copied into A[2]. Can we perform this without using a temporary array for all the elements in the array ...

I want to implement this function in simple plain C , but i just could not understand how to change the bits ...

Suggestions please...

Have you considered the Knuth Shuffle?

Here is an example in C from 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);
} 

You can change bits using the bitwise logical operators &, | etc. You can move bits using the shift << and >> operators.

It's easiest to do this using a temporary array, since otherwise how do you avoid overwriting a value you will need later?

I do not remember where I found this method (may be "Numerical recipes in C", but I cannot fint it there).

Method use bit reversed shuffle (i'll name it "bitrev" here), it reorders array elements that element index abcdef becomes fedcba (letters represent bits, 6 bit example). Three bit reverts do your functions:

1. Use two bitrevs to two halves of array, so index abcdef become afedcb (when you act on bitrev on half of array highest index bit remains the same);

2. Use bitrev on whole array, so index afedcb become bcdefa, and that's what you need.

As bitrev is easily implemented inplace this do your work.

// this function has complexity 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;
        }
}

or using templates (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;
        }
}

You may use the shuffle function with an index which is an array of char, for example:

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