Generating Random Permutations

Often I have a finite set S of objects which need to be examined in a random order without replacement. A straightforward solution would be to pick a random integer between 0 to n – 1 where n = |S| and then examine r-th element.

while (true) {
     r = rand() % n; 
     a[r] = 0; // or do some work on a[r]
}

That however leaves a possibility of consecutively drawing the same integer – an unacceptable situation in some applications. For example, if you’re trying to randomly play compositions in a music player, you’re leaving a possibility for the user to be served same composition two times in a row – a very disgruntling experience.

So instead of randomly drawing an element from S, we can map S to a sequence from 0 to n-1 and then permute the sequence, thereby generating the random permutation of S.

In the study of computer science, to my astonishment, I learned that the following approach to random permutation (i.e. shuffling) of an array wouldn’t work.

for (int i = 0; i < n; i++){
     int r = rand() % n;
     int t  = a[r];
     a[r]  = a[i];
     a[i] = t;
}

For one, what is a definition of a genuinely random permutation? Well, given n elements in a set (which must all be distinct by definition of set) you have n! permutations. Thus, if a permutation is genuinely random, it has a chance 1/n! of being generated. That defines random permutation.

Let’s see why the approach above doesn’t cut it in terms of generating a genuinely random permutation of S. Every element from 0 to n-1 is swapped with some other randomly chosen element. Such random selection results in every element having a probability of 1/n to be chosen. At the end, the entire sequence has a total probability of (1/n)^n to be generated, which is smaller than 1/(n!).

Now, the following algorithm actually does the task of generating a genuinely random shuffling and the reason is as follows: every i-th element has a 1/(n-i) of being selected (where 0 <= i < n). This is due to the way how the random element for swapping is selected.

for (int i = 0; i < n; i++){
     int r = i + rand() % (n - i - 1);
     int t = a[i];
     a[i] = a[r];
     a[r] = t;
}
Advertisements

~ by Monsi.Terdex on January 11, 2013.

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

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: