[Haskell-cafe] Output order of Data.List.permutations?

[Johannes Waldmann]

Dear Cafe -

what is the ordering of the output of
https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.OldList.html#permutations
-
and why is it not lexicographic? E.g.,

*Main> last $ L.permutations [1..8]
[5,3,6,2,7,1,8,4]

note: [5,_,6,_,7,_,8,_] and [_,3,_,2,_,1,_,4]

indeed, an auxiliary function is called "interleave".


Data.List.permutations appeared in base-4.0.0.0 (ghc-6.10.1, 2008)
https://downloads.haskell.org/~ghc/6.10.1/docs/html/users_guide/release-6-10-1.html
 What is the source of the algorithm?
Is it any of the algorithms in Knuth AOCP 4A(I) 7.2.1.2?
Hard to tell - as they are given in an imperative style.


The implementation *is* fast, e.g., L.sort . L.permutations
seems better than a naive lexicographic enumeration

lp1 [] = [[]]
lp1 xs = do
  (ys, z:zs) <- zip (L.inits xs) (L.tails xs)
  (z:) <$> lp1 (ys <> zs)

(un-scientifically measured with :set +s)
Here, clearly, L.inits and "<>" are bad.


NB - I was looking in to this because of
https://www.mathekalender.de/wp/calendar/challenges/challenge-01/
Yes I know that can be solved without enumeration.

- J.