Am Donnerstag 24 Dezember 2009 03:30:54 schrieb Patrick LeBoutillier:

> How do you do it with drinkPerms? The constant element is in the

> middle (with Nations

> it seems easier since it's the first one).

insertAt :: Int -> a -> [a] -> [a]

insertAt k x xs = case splitAt k xs of

(front,back) -> front ++ x:back

drinkPerms = map (insertAt 2 Milk) $ permutations [Coffee, Tea, Water, Beer]

Another possibility to have x inserted at a fixed position in all permutations of xs is to use

do (fs,bs) <- picks k xs

pf <- permutations fs

pb <- permutations bs

return (pf ++ x:pb)

which has the advantage that the permutations of the front are shared (if the back is longer than the front, it might be better to swap lines 2 and 3 to share the permutations of the back) and avoids the many splits.

picks :: Int -> [a] -> [([a],[a])]

picks k xs

| k == 0 = [([],xs)]

| k == l = [(xs,[])]

| k > l = []

| otherwise = pickHelper l k xs

where

l = length xs

pickHelper s t yys@(y:ys)

| s == t = [(yys,[])]

| otherwise = [(y:zs,ws) | (zs,ws) <- pickHelper (s-1) (t-1) ys]

++ [(zs,y:ws) | (zs,ws) <- pickHelper (s-1) t ys]

It's by far not as nice as keeping the first element fixed, but you can easily keep more than one position fixed. And when you have a couple more items, this approach is enormously faster than filtering.