Created
July 29, 2015 15:07
-
-
Save CharlesOkwuagwu/bf7c73dc3ddf1b8ec4e4 to your computer and use it in GitHub Desktop.
Fisher–Yates Shuffle Elixir Implemetation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
defmodule FisherYates do | |
@moduledoc """ | |
Fisher–Yates Shuffle explained and implemented in javascripy with animated demo - http://bost.ocks.org/mike/shuffle/ | |
Reference implementation: http://stackoverflow.com/a/12646864/44080 | |
Usage: | |
iex(2)> FisherYates.shuffle [1, 2, 3, 4, 5, 6, 7, 8, 9] | |
[5, 7, 8, 9, 4, 3, 6, 1, 2] | |
""" | |
def shuffle(list), do: _shuffle(list, length(list), []) | |
defp _shuffle([h|_t],1,result), do: [h|result] # when n = 1 | |
defp _shuffle(list,n,[]) do # when n = list.length | |
r=:rand.uniform(n) | |
_shuffle(List.replace_at(list, r-1, List.last(list)),n-1,[r]) | |
end | |
defp _shuffle(list,n,result) do | |
r=:rand.uniform(n) # a random number from 0 to n-1 inclusive | |
vR=Enum.at(list,r-1) # list value at r | |
vE=Enum.at(list,n-1) # list value at n-1 | |
_shuffle(List.replace_at(list, r-1, vE),n-1,[vR|result]) | |
end | |
end | |
#Question: How to make this efficient for much larger lists? (Length 100_000 above) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Question: How to make this efficient for much larger lists? (Length 100_000 above)