Shuffle card algorithm

One common programming question is how to randomly shuffle an array of numbers in-place.

variant of question:-

How would you write code to shuffle a deck of cards?

                                                   OR

write a program to generate a random permutation of array elements.

let's try to understand problem:

algorithm:

1. Start iterating the array from the last element.
2. If you are at ith element from the end, generate a random number say j,in range[0,i].
3. Swap A[i] and A[j].
4. Decrease j by 1
5. Continue till you reach the element at index 1 i.e A[1].

Generalize code:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>
     int a[] = {1, 2, 3, 4, 5, 6, 7, 8},temp,i, n = 8;
// A function to generate a random permutation of a[]
void randomize ( )
{

// srand()--> gives the random function a new seed, a starting point 
//(usually random numbers are calculated by taking the previous number 
//(or the seed) and then do many operations on that number to generate the next).
 
//time(0)--> gives the time in seconds since the Unix epoch, 
//which is a pretty good "unpredictable" seed 
//(you're guaranteed your seed will be the same only once, 
//unless you start your program multiple times within the same second).
    srand ( time(NULL) );
 
    //We don't need to run for the first element that's why n-1 pass
    
    for ( i = n-1; i > 0; i--) //for Shuffle card algorithm i=51
    {
        // Pick a random index from 0 to i
        int j = rand() % (i+1);
 
        // Swap a[i] with the element at random index
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
    }
}
 
int main()
{
 // shuffle the array
    randomize ();
  // print results.
     for ( i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

output:-

8 1 5 4 6 2 3 7

time complexity:-  O(n)
time complexity to traverse array is o(n) and assume rand() generates random number in O(1) time.

code for  shuffle deck of cards: 
we have to make change in input and array size of above generalize algorithm.input array consist of 52 cards

          int a[] ={  1,2,3,4,5,6,7,8,9,10,11,12,13,
                      14,15,16,17,18,18,20,21,22,23,24,25,26,
                      27,28,29,30,31,32,33,34,35,36,37,38,39,
                      40,41,42,43,44,45,46,47,48,49,50,51,52
                   };

change value of n

int n=52  // array size 

final code for  shuffle deck of cards:  :

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>
// Clubs->1 to 13
//Diamonds->14 to 26
//Hearts->27 to 39
//Spades->40 to 52
 int a[] ={ 1,2,3,4,5,6,7,8,9,10,11,12,13,
            14,15,16,17,18,18,20,21,22,23,24,25,26,
            27,28,29,30,31,32,33,34,35,36,37,38,39,
            40,41,42,43,44,45,46,47,48,49,50,51,52
          };
 int temp,i, n = 52;
// A function to generate a random permutation of a[]
void randomize ( )
{
 
// srand()--> gives the random function a new seed, a starting point 
//(usually random numbers are calculated by taking the previous number 
//(or the seed) and then do many operations on that number to generate the next).
  
//time(0)--> gives the time in seconds since the Unix epoch, 
//which is a pretty good "unpredictable" seed 
//(you're guaranteed your seed will be the same only once, 
//unless you start your program multiple times within the same second).
    srand ( time(NULL) );
  
    //We don't need to run for the first element that's why n-1 pass
     
    for ( i = n-1; i > 0; i--) //for Shuffle card algorithm i=51
    {
        // Pick a random index from 0 to i
        int j = rand() % (i+1);
  
        // Swap a[i] with the element at random index
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
    }
}
  
int main()
{
 // shuffle the array
    randomize ();
  // print results.
     for ( i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

output:-

29 8 47 10 49 28 24 43 14 13 48 32 2 12 
36 31 30 18 50 1 25 41 40 45 39 38 6 35
23 17 9 46 20 11 51 52 4 34 42 15 22 7 
37 33 18 3 5 16 27 26 21 44

SHARE