It’s been a long time I have done any activity in this blog. I was going through some old stuffs and thought to post something. Today I will post a generic implementation for Fisher-Yates Shuffle.

Although you can get the Fisher-Yates algorithm from wiki, still I am briefly explaining it.

Let us assume that there is a array arr of length n. We need to find a uniformly random permutation of the elements of the array. One of the variations of the algorithm is as follows.

arr is an array of length n, where indexing starts from 0
i=n-1
while i>0
{
  r = generate a random number between 0 and i (both inclusive)
  swap the array elements arr[r] and arr[i]
  i = i - 1
}
arr is now uniformly permuted

The i is the index where the list is seperated between yet-to-be-selected and selected elements. At each iteration the working length i of the list is decreased. One element from the current list is picked up uniformly randomly and then placed at the end of the list, by the swap and list length decrease operation.

For example. Let us assume we have a list of arr[] = {1, 2, 3, 4, 5, 6} . In the illustration below the | indicates the current end of the working list.

arr[] = {1, 2, 3, 4, 5, 6}, n = 6;

The brackets below indicate the elements to swap

1, 2, [3], 4, 5, [6] |   i=5, r = rand (0, 5) = 2, swap (arr[i], arr[r]), i--
1, 2, 6, [4], [5]| 3     i=4, r = rand (0, 4) = 3, swap (arr[i], arr[r]), i--
[1], 2, 6, [5]| 4, 3     i=3, r = rand (0, 3) = 0, swap (arr[i], arr[r]), i--
5, [2], [6]| 1, 4, 3     i=2, r = rand (0, 2) = 1, swap (arr[i], arr[r]), i--
[5], [6]| 2, 1, 4, 3     i=1, r = rand (0, 1) = 0, swap (arr[i], arr[r]), i--
6  | 5  , 2, 1, 4, 3         i=0 terminate

Shuffled list: arr[] = {6, 5, 2, 1, 4, 3};

In the above example we have an initial list. At any given step the algorithm generates a random number in range [0,i], where i is the current working length of list. The working length of the list indicates, how many elements of the original lists are yet to be selected to generate the shuffled list. Therefore the array range [0,i] indicates the yet to be shuffled list, and [i+1,n-1] indicates the shuffled list. At the last step when there is only one element, there is only one place where we can put it, and no swap is required, and the algorithm terminates. For example, when i=2 we have list [0,2] yet to be shuffled into the list and the shuffled list is in [3,5].

Basic implementation

Let’s give the initial quick implementation for an shuffling for an integer array.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap (int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

void fy_shuffle (int *arr, int n)
{
  int r;

  srand (time (NULL));
  while (n)
  {
    r = rand () % n;
    swap (arr + (n - 1), arr + r);
    n--;
  }
}

int main (int argc, char *argv[])
{
  int *arr;
  int n, i;

  if (argc != 2)
  {
    return 0;
  }

  n = atoi (argv[1]);
  if ((n <= 0) || (n > 100)) return 0; /* Limit stuffs */
  arr = malloc (sizeof (int) * n);
  for (i=0; i<n; i++)
  {
    arr[i] = i;
  }
  printf ("before: "); for (i=0; i<n; i++) printf ("%d ", arr[i]); printf ("\n");
  fy_shuffle (arr, n);
  printf ("after : ");  for (i=0; i<n; i++) printf ("%d ", arr[i]); printf ("\n");

  free (arr);
  return 0;
}

The function fy_shuffle is the implementation of the Fisher-Yates shuffle. Provide the length of the list within range [1,100], and the main function generates an identity array which it shuffles by calling fy_shuffle.

Generic implementation

This function fy_shuffle with integer only. It would have been better if we could use this function like the functions qsort or bsearch which can work with any type of structures. To make the fy_shuffle work like that, we can pass the array as a void * but the problem will be the type of elements will be unknown in the swap function. For exmaple if we want to shuffle an array of structures, then we need to swap structures, and once it is void * and we do not know the type of structure.

The only problem here is the swap step, were we need to swap element by element, and the element will depend on the size of the type of the elements of the array. The simple answer is to block swap bytes. Let us assume that the array has a base address base with n elements and the size of each element is s then when we indicate the ith element using ((char *)base + (i * s)). Here we access the base address of the array byte by byte and because we know the width of the type, s, we can use jump multiples of s bytes to jump to the next element base address. I will use this idea to implement a generic block swap and incorporate it into the generic Fisher-Yates function as follows.

void shuffle (void *base, size_t nel, size_t width)
{
  int r;
  char *temp;

  temp = malloc (sizeof (width));
  srand (time (NULL));
  while (nel)
  {
    r = rand () % nel;
    /* Block swap */
    memcpy (temp, (char *) base + r * width, width);
    memcpy ((char *) base + r * width, (char *) base + (nel - 1) * width, width);
    memcpy ((char *) base + (nel - 1) * width, temp, width);
    nel--;
  }

  free (temp);
}

Above highlighted lines are the generic block swap. Let me explain the memcpys a bit. Because we know the base address, number of elements of the specific type and the width of the type, we do not need to know the actual type to do the swap operation.

The first memcpy will copy width number of bytes from base + r * width to temp. Here base + r * width points to the base address of the rth element in the list of whatever type. Similarly the second memcpy transfers width number of bytes into the rth element of the list from the last element of the current working list, which is indexed with (nel-1). The last memcpy transfers the temp to the (nel-1)th element. Basically the memcpy works as a block assignment operator. As we know the width of the type, we don’t care about the type itself.

The invocation will be as follows.

shuffle (arr, n, sizeof (int));

I have a small example for this with a structure as follows.

struct my_struct
{
  char a, b, c, d, e;
};

int main (void)
{
  int arr[] = {1, 2, 3, 4, 5, 6};
  int n = 6, i;
  struct my_struct obj[6] =  { {'a', 'b', 'c', 'd', 'e'},
                               {'f', 'g', 'h', 'i', 'j'},
                               {'k', 'l', 'm', 'n', 'o'},
                               {'p', 'q', 'r', 's', 't'},
                               {'u', 'v', 'w', 'x', 'y'},
                               {'z', '1', '2', '3', '4'}
                             };

  /* Test with integer shuffling */
  for (i=0; i<n; i++) printf ("%d ", arr[i]); printf ("\n");
  shuffle (arr, n, sizeof (int));
  for (i=0; i<n; i++) printf ("%d ", arr[i]); printf ("\n");


  /* Shuffle structure array */
  for (i=0; i<n; i++)
  {
    printf ("%c %c %c %c %c\n", obj[i].a, obj[i].b, obj[i].c, obj[i].d, obj[i].e);
  }
  printf ("\n");
  shuffle (obj, n, sizeof (struct my_struct));
  for (i=0; i<n; i++)
  {
    printf ("%c %c %c %c %c\n", obj[i].a, obj[i].b, obj[i].c, obj[i].d, obj[i].e);
  }

  return 0;
}

Use the above code with the shuffle function to see the results. The output for the structures should have the structure elements in shuffled order and the elements should not be mixed.

Complexity

The shuffle is done in-place, therefore the growth of required space is constand with respect to the number of elements in the list. As the array is traversed only once, and each element is processed once, the growth of the time is O(n), therefore this algorithm works in linear time with respect to the number of elements in the list.

On Linked list

This can be extended on linked list, but as we need to seek to the rth, and in linked list we need to start from the head of the list, the time complexity will not be O(n) anymore. For linked list in the worst case, at each step the last element of the list can be selected for which we have (n*(n+1))/2> node visits in total, which makes the worst case O(n^2). If we expect in an average at each iteration the random number generated will be (i-0)/2, then also the upper-bound growth will be the same.

Portability and Issues

Are we introducing any kind of portability issues? I do not think so. This is because the code is not dependent on the byte ordering and/or the padding inside the structures (if any). The memcpy is done using the bytes as is, and the internal structures of the bytes are not being accessed or modified in any way. Because the starting address of each element in an given array and index is guranteed, therefore this code will work always.

One obvious issue is with the srand initialization, if the fy_shuffle or the shuffle is called more than once in within one second, such that time (NULL) returns the same value, then the multiple calls of fy_shuffle or shuffle on the same array will result in identical results. To overcome this we can get a better seed generator, maybe pick a seed from /dev/random, or use the gettimeofday function and use microseconds value to initialize the random number generator. Although this will stop it from being portable from *nix and Windows.

If you think there is something I have missed here, let me know in the comments.

References

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s