Skip to content

Instantly share code, notes, and snippets.

@robertmryan
Last active October 8, 2017 20:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save robertmryan/b002b7d524646fd677bb3979c89ec331 to your computer and use it in GitHub Desktop.
Save robertmryan/b002b7d524646fd677bb3979c89ec331 to your computer and use it in GitHub Desktop.
Shuffle: Fisher-Yates vs Naive Shuffles (Swift 4)
extension Array {
/// Simple implementation of Fisher-Yates
mutating func shuffle() {
for i in 0 ..< count - 1 {
let j = i + Int(arc4random_uniform(UInt32(count - i)))
swapAt(i, j)
}
}
/// Naive implementation that introduces biases
mutating func shuffleBiased() {
for i in 0 ..< count {
let j = Int(arc4random_uniform(UInt32(count)))
swapAt(i, j)
}
}
}
@robertmryan
Copy link
Author

robertmryan commented Oct 8, 2017

The naive shuffle algorithm generates a very biased result. For example, shuffling an array of 10 numbers 10,000,000 times resulted in a distribution of:

biased

Whereas Fisher-Yates algorithm results in the following distribution:

fy

@robertmryan
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment