Shuffling algorithm produces biaised permutation

[mratsim]

The shuffling algorithm in the standard library is biaised and does not produce evenly distributed permutations.

Nim/lib/pure/random.nim

Lines 567 to 580 in f1a8edc

	proc shuffle*[T](r: var Rand; x: var openArray[T]) =
	## Shuffles a sequence of elements in-place using the given state.
	##
	## See also:
	## * `shuffle proc<#shuffle,openArray[T]>`_ that uses the default
	## random number generator
	runnableExamples:
	var cards = ["Ace", "King", "Queen", "Jack", "Ten"]
	var r = initRand(678)
	r.shuffle(cards)
	doAssert cards == ["King", "Ace", "Queen", "Ten", "Jack"]
	for i in countdown(x.high, 1):
	let j = r.rand(i)
	swap(x[i], x[j])

It should implement an unbiaised pseudo-random permutation algorithm instead, here are some propositions:

• Fisher-Yates
• Thorp shuffle
• Feistel shuffle
• Permutator Shuffle
• Swap-or-not

The most well known is Fisher-Yates, also often called Knuth Shuffle.

See in-depth explanations with demos:

• How not to shuffle
• Randomness is hard

Here are implementations in Python of Fisher-Yates, Prime shuffling, Feistel Shuffling and Swap-or-not shuffling: https://github.com/ethereum/research/tree/260faf622ef5e8e84bda1258a9f98956baf72991/shuffling

[Araq]

I fail to see how the stdlib's implementation differs from what https://medium.com/@oldwestaction/randomness-is-hard-e085decbcbb2 describes

[narimiran]

I did a quick test of Nim's shuffle frequencies based on the article @Araq linked:

For the first test ("300k tries on a 4-item set"):

expected: 12500 (one in 24)
smallest: 12339 (one in 24)
largest:  12694 (one in 23)

For the second test ("1 million tries on a 6-item set"):

expected: 1388 (one in 720)
smallest: 1269 (one in 788)
largest:  1491 (one in 670)

Both examples show quite uniform distribution. Closing.