David Benbennick wrote:
Actually, I would like permutations to satisfy: map (take n) (take (factorial n) $ permutations [1..]) == permutations [1..n]
Twan van Laarhoven wrote:
permutations5 xs = xs : perms xs [[]] where perms [] ps = [] perms (x:xs) ps = concatMap interleave' ps ++ perms xs (concatMap interleave ps) where interleave [] = [[x]] interleave (y:ys) = (x:y:ys) : map (y:) (interleave ys) interleave' [] = [] interleave' (y:ys) = (x:y:ys++xs) : map (y:) (interleave' ys)
Twan, I think you are working a little too hard to satisfy the consistency property. You only need to satisfy it for permutations where the first n elements of the permutation are the same as the first n elements of the original list. Other than that, you can just use the faster function that you defined earlier. Here is a quick effort that beats permutations5 by using your previous permutations3: permutations7 xs = xs : (concat $ zipWith newPerms (init $ tail $ tails xs) (init $ tail $ inits xs)) where newPerms (t:ts) = map (++ts) . concatMap (interleave t) . permutations3 interleave t [y] = [[t, y]] interleave t ys@(y:ys') = (t:ys) : map (y:) (interleave t ys') (sorry about using the name interleave yet again, ugh) On my machine the result is: control: 1.037048 sec permutations3: 1.4078301 sec permutations5: 3.280238 sec permutations7: 3.0912578 sec