Uniformly distributed random permutations
Posted: Sun Sep 20, 2009 11:47 am
Works also with PB 5.20
Hi all,
like in many other programming languages, PureBasic's built-in Random() function returns uniformly distributed random numbers with repetition. In other words, it mimics random processes that work like a die: When a die shows e.g a "6", then the "6" will not be removed from the die, so it can show a "6" again any time in the future. This is what programs that use randomness often need.
However, there are also programs that mimic other processes, where uniformly distributed random numbers without repetition are needed. Think for instance of a lottery: When a particular lottery ticket has been drawn, it is removed from the game and cannot be drawn again. A computer lottery program needs to randomly rearrange the lottery tickets. In other word, is has to create random permutations. This is also needed e.g. for shuffling a deck of cards.
Implicit in many every day use of the word "random" is the fact that the draw should be fair or unbiased, and especially games of hazard are expected to be fair for obvious reasons. So here we want to generate random permutations, that all have the same chance to be drawn. This is the classic algorithm:
An example of the Knuth shuffle with detailed analysis is in my file shuffle.pdf.The probability tree shows that the procedure is fair.
You might wonder whether it makes sense to put a simple thing such as the Knuth shuffle in the "Tricks 'n' Tips" section here. My reason for posting it here is, that it's only simple if you know the solution.
I often see wrong approaches to this problem, resulting in code that produces biased results which are not uniformly distributed.
A common mistake is to use
instead of
An analysis of this biased algorithm is given in the PDF file on the page "Unfair shuffle #1".
Since we want to get random numbers without repetition, the mistake is obvious here: When we have "drawn" an element by swapping it to the last part of the array, we must take care that next time the Random() function cannot return the index of this element again. So the first part of the array from where an element will be drawn must be reduced by one on each step.
Another wrong approach to the problem that I have seen is shown in the PDF file on the page "Unfair shuffle #2".
Enjoy, Little John
Hi all,
like in many other programming languages, PureBasic's built-in Random() function returns uniformly distributed random numbers with repetition. In other words, it mimics random processes that work like a die: When a die shows e.g a "6", then the "6" will not be removed from the die, so it can show a "6" again any time in the future. This is what programs that use randomness often need.
However, there are also programs that mimic other processes, where uniformly distributed random numbers without repetition are needed. Think for instance of a lottery: When a particular lottery ticket has been drawn, it is removed from the game and cannot be drawn again. A computer lottery program needs to randomly rearrange the lottery tickets. In other word, is has to create random permutations. This is also needed e.g. for shuffling a deck of cards.
Implicit in many every day use of the word "random" is the fact that the draw should be fair or unbiased, and especially games of hazard are expected to be fair for obvious reasons. So here we want to generate random permutations, that all have the same chance to be drawn. This is the classic algorithm:
Code: Select all
Procedure Shuffle (Array a(1))
; -- "Knuth shuffle"
; linear-time algorithm for generating uniformly distributed
; random permutations
Protected last, i, r
last = ArraySize(a())
For i = last To 1 Step -1
r = Random(i)
Swap a(i), a(r)
Next
EndProcedure
;-- Demo
Define ret$, i, n=4
Dim a(n-1)
For i = 0 To n-1
a(i) = i
Next
Shuffle(a())
ret$ = Str(a(0))
For i = 1 To n-1
ret$ + "," + Str(a(i))
Next
Debug ret$You might wonder whether it makes sense to put a simple thing such as the Knuth shuffle in the "Tricks 'n' Tips" section here. My reason for posting it here is, that it's only simple if you know the solution.
I often see wrong approaches to this problem, resulting in code that produces biased results which are not uniformly distributed.A common mistake is to use
Code: Select all
r = Random(last)Code: Select all
r = Random(i)Since we want to get random numbers without repetition, the mistake is obvious here: When we have "drawn" an element by swapping it to the last part of the array, we must take care that next time the Random() function cannot return the index of this element again. So the first part of the array from where an element will be drawn must be reduced by one on each step.
Another wrong approach to the problem that I have seen is shown in the PDF file on the page "Unfair shuffle #2".
Enjoy, Little John
