Add 'subsequences' and 'permutations' to Data.List (ticket #1990)

[Yitzchak Gale]

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