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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: