Uniformly distributed random permutations

Share your advanced PureBasic knowledge/code with the community.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Uniformly distributed random permutations

Post by Little John »

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:

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$
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

Code: Select all

r = Random(last)
instead of

Code: Select all

r = Random(i)
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
Last edited by Little John on Mon Aug 19, 2013 3:35 pm, edited 1 time in total.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Uniformly distributed random permutations

Post by Little John »

How the Knuth shuffle works

Say we have an array that contains 6 numbered elements in ascending order.
For better understanding, it might help when we think of the array as consisting of two parts, say the "drawing area" and the "randomized area". At the beginning, it looks like this:

Code: Select all

     drawing area     | randomized area
----------------------+----------------
0 | 1 | 2 | 3 | 4 | 5 | <empty>
We are going to do repeatedly the following (For i = 5 to 1 Step -1):

Code: Select all

r = Random(i)
Swap a(r), a(i)
We are starting with i = 5. Let's assume our first value of r is 3. Then after swapping, the array looks like this:

Code: Select all

   drawing area   | randomized area
------------------+----------------
0 | 1 | 2 | 5 | 4 | 3
That means we have drawn number 3 randomly from all given elements by r = Random(5). Then, like in a lottery, this element shouldn't be drawn again. So we "put it aside", and at the same time we take care that number 5 is still part of the game by doing Swap a(3), a(5). Since one element (number 3) has been removed from the "drawing area", the value of i has to be decreased by 1 for the next Random() command.

Now i = 4, and say our second value of r is 1. Then after swapping, the array looks like this:

Code: Select all

drawing area  | randomized area
--------------+----------------
0 | 4 | 2 | 5 | 1 | 3
Get the picture?
The process might continue like this:

i = 3
r = 3 (for example)

Code: Select all

drawing   | randomized area
  area    |
----------+----------------
0 | 4 | 2 | 5 | 1 | 3
i = 2
r = 1 (for example)

Code: Select all

drawing | randomized area
  area  |
--------+----------------
  0 | 2 | 4 | 5 | 1 | 3
i = 1
r = 0 (for example)

Code: Select all

drawing |   randomized area
  area  |
--------+----------------------
<empty> | 2 | 0 | 4 | 5 | 1 | 3
Now all elements have been drawn in a randomized way, i.e. the array has been shuffled.

Regards, Little John
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Uniformly distributed random permutations

Post by Little John »

<reserved> 8)
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Uniformly distributed random permutations

Post by Little John »

<reserved> 8)
rsts
Addict
Addict
Posts: 2736
Joined: Wed Aug 24, 2005 8:39 am
Location: Southwest OH - USA

Re: Uniformly distributed random permutations

Post by rsts »

Very interesting.

Thanks for taking the time to share and explain.

cheers
WilliamL
Addict
Addict
Posts: 1215
Joined: Mon Aug 04, 2008 10:56 pm
Location: Seattle, USA

Re: Uniformly distributed random permutations

Post by WilliamL »

I've been trying to understand how the Knuth Shuffle works and got more and more confused as I played with your code. It appears that you are using a(0) but your For/Next loops are using 1 to 5 then you list them out using a(0)=ret$ and loop only to 4. :shock:

So I played with it and came up with this. I'm dealing cards so each card has to have a number (no zero card). Since Random() can give a zero I just subtracted 1 from i and then added 1.

Does this make any sense?

Code: Select all

Define MaxList=5 ; zero not used (1,2,3,4,5 used)
Dim a(MaxList)
For cnt=1 To MaxList
    A(cnt)=cnt ; assign card values
Next

Procedure Shuffle (Array a(1))
   ; -- "Knuth shuffle" linear-time algorithm For generating uniformly distributed random permutations
   Protected last, i, r

   last = ArraySize(a()) : Debug "Array size="+Str(last)
   For i = last To 1 Step -1
      r = Random(i-1)+1 : Debug "r="+Str(r)
      Swap a(i), a(r)
   Next
EndProcedure

Shuffle(a()) ; shuffle cards

For cnt=1 To MaxList
    Debug Str(cnt)+" "+Str(A(cnt))
Next
MacBook Pro-M1 (2021), Sonoma 14.3.1 (CLT 15.3), PB 6.10b7 M1
User avatar
jacdelad
Addict
Addict
Posts: 1436
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Uniformly distributed random permutations

Post by jacdelad »

I hope I can explain it:
The code is correct. The array starts at 0, an array defined as "array(2)" has 3 elements: 0, 1 and 2. Arraysize will return 2, this is the last element. The count of elements is arraysize+1 (as written in the help file!).
"Random(i)" gives you a randomized number from 0 to i-1, because internally it's a fraction between 0 and lower than one (multiplied with i, so it's always lower than i). Random(3) can give you 0, 1 or 2.

Your array starts at 1, which is unusual. If you wish to start it at 1 (which leaves the first item unused) you have to correct you randomizing algorithm:
"Random(i-1)+1" is wrong, because you still have "i" elements. The correct one is "Random(i)+1" or "Random(i)+j", with "j" being the first element used (1 in your case).

I hope this helps, I'm not good at explaining...
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
User avatar
Demivec
Addict
Addict
Posts: 4086
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Re: Uniformly distributed random permutations

Post by Demivec »

jacdelad wrote: Thu Nov 18, 2021 1:56 am"Random(i)" gives you a randomized number from 0 to i-1, because internally it's a fraction between 0 and lower than one (multiplied with i, so it's always lower than i). Random(3) can give you 0, 1 or 2.
@jacdelad: Your info on PureBasic's Random() is incorrect.
Help file wrote:Returns a random number from zero to the given maximum value (both values included).
This means Random(3) will give 0 1, 2 and 3.
User avatar
jacdelad
Addict
Addict
Posts: 1436
Joined: Wed Feb 03, 2021 12:46 pm
Location: Planet Riesa
Contact:

Re: Uniformly distributed random permutations

Post by jacdelad »

Damn, you're right. Sorry for that misinformation. So it should be "Random(i,1)".
PureBasic 6.04/XProfan X4a/Embarcadero RAD Studio 11/Perl 5.2/Python 3.10
Windows 11/Ryzen 5800X/32GB RAM/Radeon 7770 OC/3TB SSD/11TB HDD
Synology DS1821+/36GB RAM/130TB
Synology DS920+/20GB RAM/54TB
Synology DS916+ii/8GB RAM/12TB
kvitaliy
Enthusiast
Enthusiast
Posts: 162
Joined: Mon May 10, 2010 4:02 pm

Re: Uniformly distributed random permutations

Post by kvitaliy »

RandomizeArray gives a similar result:

Code: Select all

;-- Demo
Define ret$, i, n=4

Dim a(n-1)
For i = 0 To n-1
   a(i) = i
Next

;Shuffle(a())
RandomizeArray(a())

ret$ = Str(a(0))
For i = 1 To n-1
   ret$ + "," + Str(a(i))
Next
Debug ret$
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Uniformly distributed random permutations

Post by Little John »

@WiliamL:
My Shuffle() procedure always shuffles the whole concerning array.
So if you want to shuffle say array a() with x elements, you have to use

Code: Select all

Dim a(x-1)
PureBasic's arrays always start with index 0, see https://www.purebasic.com/documentation ... e/dim.html

Ignoring one of the array elements doesn't make sense when using my Shuffle() procedure. Note that the values of your array elements are independent from the indexes of the elements!
For shuffling e.g. the values 100, 200, and 300, just do this:

Code: Select all

Dim x(2)
x(0) = 100
x(1) = 200
x(2) = 300
Shuffle(x())
You see that using index 0 isn't any problem at all.
kvitaliy wrote:RandomizeArray gives a similar result:
Yep. RandomizeArray() was introduced in PureBasic version 4.60 (November 2011). I couldn't foresee that when I posted the Shuffle() procedure here in September 2009. :-)

BTW: In contrast to my Shuffle() procedure, RandomizeArray() does not neccessarily randomize the whole array, but you can choose a start and end index, if you want.
Jeff8888
User
User
Posts: 38
Joined: Fri Jan 31, 2020 6:48 pm

Re: Uniformly distributed random permutations

Post by Jeff8888 »

Out of curiosity I compared "Shuffle" to RandomizeArray for array of 52 elements. Obtained similar results after I disabled debugging for the Shuffle Procedure. Still amazes me how fast a PC is these days. For a million shuffles I got 0.41 secs for "Shuffle" and 0.37 secs for RandomizeArray.
Took above code and modified for this test.

Code: Select all

DisableDebugger
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

n=52

Dim a(n-1)
For i = 0 To n-1
   a(i) = i
Next
time=ElapsedMilliseconds()
For i=1 To 1000000
Shuffle(a())        
;RandomizeArray(a())
Next
EnableDebugger
Debug (ElapsedMilliseconds()-time)/1000.0
Post Reply