defmodule Knuth do
  @moduledoc """
  The Elixir implementation of the Knuth shuffle(a.k.a Fisher Yates shuffle) algorithm.
  """

  @doc """
  
  """
  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