Knuth shuffle

This code has been declared by its author to be Public Domain code.

Knuth shuffle by Warpy

2008

Suppose you have a set of things you want to shuffle up, like a deck of cards, or a list of players so they take turns in a random order.

Mathematically speaking, what this is doing is generating a permutation of order n.

It's much much much faster than the brute-force method that springs immediately to mind.

'takes as input the number of elements you want to shuffle, and returns an array saying which
'elements to swap with which
'i.e. when this is done you should swap element i with element k[i]
Function KnuthShuffle[](n)
	Local k[n]
	For i=0 To n-1
		k[i]=i
	Next
	
	For i=0 To n-2
		j=Rand(i,n-1)
		b=k[i]
		k[i]=k[j]
		k[j]=b
	Next
	
	Return k
End Function

'an example - shuffle up the letters in a string
SeedRnd MilliSecs()
s$="abcdefg"
o$=""
For i=EachIn knuthshuffle(Len(s))
	o:+Chr(s[i])
Next
Print o

Comments

Chroma

2013

Thanks Warpy. I just ported this to Monkey and I'm using it to shuffle objects in a stack. Works a treat!

Code Archives Forum