Sunday, February 26, 2012

Random Set Shuffling

 Linear In-Place Shuffling :

The modern version of Fisher–Yates shuffle ( aka Knuth shuffle) can be used for generating a random permutation of a finite set or for randomly shuffling  a set. Fisher–Yates shuffle is unbiased, so that every permutation is equally likely.

Pseudocode :
A[n] : An array of n elements
for i  from n − 1 to 1 do
       j ← random integer with 0 ≤ ji
       swap A[j] and A[i]

This algorithm's time complexity  is O(n).

Generation of a New Shuffled Set from a Source Set:

Inside-out algorithm simultaneously initializes and shuffles an array from a given source array.

Pseudocode :
Source[n] // Source array
A[n] // Target array 
A[0] ← Source[0]
for i from 1 to n − 1 do
      j ← random integer with 0 ≤ ji
      A[i] ← A[j]
      A[j] ← Source[i]
 
This algorithm's time complexity  is O(n).
These algorithms are also used for randomly shuffling playing cards in electronic computer games.

No comments:

Post a Comment