Shuffle function in C

Question

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 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...

@John : nopes... i could do it using a temporary array , but i wanted to know if we can do it without a temporary array ... — Flash, Nov 17 '10 at 13:32

score 1 · Answer 1 · answered Jan 18 '12 at 07:17

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

score 0 · Answer 2 · answered Nov 17 '10 at 13:35

0

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?

answered Nov 17 '10 at 13:35

Alex Brown

41,819
10
94
108

score 0 · Answer 3 · edited May 23 '17 at 11:52

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:

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);
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.

angleto · Answer 4 · 2010-11-17T14:52:25.350

-1

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

edited Nov 17 '10 at 14:52

answered Nov 17 '10 at 14:26

angleto

114
4

There is nothing random about this shuffle. – A T Jan 18 '12 at 07:15
you are right, but the question does not require a random shuffle – angleto Feb 26 '12 at 20:44
[shuffle](http://www.merriam-webster.com/dictionary/shuffle) means: `to mix in a mass confusedly : jumble` – A T Feb 28 '12 at 07:28
the meaning of the word shuffle is not under discussion. I answered to the question posted *here*, despite that the word "shuffle" is used, in the question seems clear that randomness is **not wanted**. However in the same page [shuffle](http://www.merriam-webster.com/dictionary/shuffle) at the point 3.b says: "to move about, back and forth, or from one place to another". – angleto Feb 28 '12 at 17:03
Yeah, point 3. When you see the word shuffle you immediately associate it with random. – A T Feb 29 '12 at 06:32

Shuffle function in C

4 Answers4