Skip to content

Instantly share code, notes, and snippets.

@CharlesOkwuagwu
Created July 29, 2015 15:07
Show Gist options
  • Save CharlesOkwuagwu/bf7c73dc3ddf1b8ec4e4 to your computer and use it in GitHub Desktop.
Save CharlesOkwuagwu/bf7c73dc3ddf1b8ec4e4 to your computer and use it in GitHub Desktop.
Fisher–Yates Shuffle Elixir Implemetation
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)
@CharlesOkwuagwu
Copy link
Author

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