Hello Everyone,
Given an array, write a program to generate a random permutation of array elements. This question is also asked as “shuffle a deck of cards” or “randomize a given array”. Here shuffle means that every permutation of array element should equally likely.
Let the given array be arr[] . A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[] . Randomly select an element from temp[] , copy the randomly selected element to arr[0] and remove the selected element from temp[] . Repeat the same process n times and keep copying elements to arr[1], arr[2], … . The time complexity of this solution will be O(n^2).
Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates random number in O(1) time.
The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.
Following is the detailed algorithm
To shuffle an array a of n elements (indices 0…n-1): for i from n - 1 downto 1 do j = random integer with 0 <= j <= i exchange a[j] and a[i]
Following is implementation of this algorithm.
// C++ Program to shuffle a given array
#include<bits/stdc++.h>
#include <stdlib.h>
#include <time.h>
using
namespace
std;
// A utility function to swap to integers
void
swap (
int
*a,
int
*b)
{
int
temp = *a;
*a = *b;
*b = temp;
}
// A utility function to print an array
void
printArray (
int
arr[],
int
n)
{
for
(
int
i = 0; i < n; i++)
cout << arr[i] <<
" "
;
cout <<
"\n"
;
}
// A function to generate a random
// permutation of arr[]
void
randomize (
int
arr[],
int
n)
{
// Use a different seed value so that
// we don't get same result each time
// we run this program
srand
(
time
(NULL));
// Start from the last element and swap
// one by one. We don't need to run for
// the first element that's why i > 0
for
(
int
i = n - 1; i > 0; i--)
{
// Pick a random index from 0 to i
int
j =
rand
() % (i + 1);
// Swap arr[i] with the element
// at random index
swap(&arr[i], &arr[j]);
}
}
// Driver Code
int
main()
{
int
arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
randomize (arr, n);
printArray(arr, n);
return
0;
}
Output :
7 8 4 6 3 1 2 5
The above function assumes that rand() generates a random number.
Time Complexity: O(n), assuming that the function rand() takes O(1) time.
How does this work?
The probability that ith element (including the last one) goes to last position is 1/n, because we randomly pick an element in first iteration.
The probability that ith element goes to second last position can be proved to be 1/n by dividing it in two cases.
Case 1: i = n-1 (index of last element) :
The probability of last element going to second last position is = (probability that last element doesn’t stay at its original position) x (probability that the index picked in previous step is picked again so that the last element is swapped)
So the probability = ((n-1)/n) x (1/(n-1)) = 1/n
Case 2: 0 < i < n-1 (index of non-last) :
The probability of ith element going to second position = (probability that ith element is not picked in previous iteration) x (probability that ith element is picked in this iteration)
So the probability = ((n-1)/n) x (1/(n-1)) = 1/n
We can easily generalize above proof for any other position.