design notes on the permutation algorithm
authorCarter Tazio Schonwald <carter.schonwald@gmail.com>
Tue, 30 May 2017 02:39:32 +0000 (22:39 -0400)
committerCarter Tazio Schonwald <carter.schonwald@gmail.com>
Tue, 30 May 2017 02:39:32 +0000 (22:39 -0400)
src/Data/Distribution/Permutation.hs

index dd84b04..83a8b48 100644 (file)
@@ -1,2 +1,17 @@
 module Data.Distribution.Permutation where
 
+import Control.Monad.Primitive
+{- | this permutation algorithm is due to knuth.
+
+to construct a permutation of n symbols, @0... n-1@
+
+initialize a size n array A with position @i@ having value @i@
+
+(may choose to precompute the sequence of permutations before setting up the array)
+
+forM [1 .. n-1] \j ->  pick a uniform sample s from the interval [j, n-1],
+then swap the values at A[j-1] and A[s]
+
+return the array A
+-}
+--samplePermutation :: Monad m =>