# Permutations with constraints

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.