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