Add 'subsequences' and 'permutations' to Data.List (ticket
#1990)
Yitzchak Gale
gale at sefer.org
Thu Dec 20 17:41:17 EST 2007
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
More information about the Libraries
mailing list