In order to apply constraints while generating permutations, I needed a new algorithm. Haskell’s library function Data.List.permutations builds permutations using interleave, so each item added could end up anywhere in the list. I needed items to stay in the same place once chosen.
{-
Stable permutation: once elements have been picked, they stay in the same place (measured from the end) while the remainder is permuted.
Intermediate results include recursion depth to facilitate filtering.
-}
permute::[a]->[[a]]
permute xs = map fst $ permute' (length xs) [([],xs)]
permute'::Int->[([a],[a])] -> [([a],[a])]
permute' 0 xs = xs
permute' depth xs = permute' (depth - 1) $ concat $ map permute'' xs
-- generate the next level of permutation of a single item
permute''::([a],[a])->[([a],[a])]
permute'' (xs,ys) = map (\(y,y')->((y:xs),y')) $ picks ys
-- generate all the ways to pick one item from a list
picks::[a]->[(a,[a])]
picks xs = map picks' $ splits xs
picks'::([a],[a]) -> (a,[a])
picks' (xs, ys) = ((head ys),(xs ++ tail ys))
-- generate all the ways to split a list
splits::[a]->[([a],[a])]
splits [] = []
splits (x:xs) = ([],x:xs):[(x:ls,rs) | (ls,rs)<-splits xs]
Note that this performs much worse than Data.List.permutations, because it has to keep track of remaining items for every permutation generated.
In my next post, I apply constraints and use them to solve the magic square problem.
Great Wall 