July 15th, 2010


every once in a while, Haskell does make me happy

Pursuant to the previous entry (deliberately omitting some keywords), today I wrote a thing to find the nth permutation of a list in lexicographic order. I started by thinking about how to enumerate all the permutations. In Knuth's fascicle on the topic (, there's a multiparagraph description of a procedural algorithm, and it feels really clunky, as procedural algorithms often do. Trying to squeeze this into Haskell (or indeed write it at all) hurt my brain until I took a moment to experiment with a naive recursive approach, which was correct immediately and didn't hurt at all.

First, some utility functions. Given a list, the "breaks" function does a break at each possible place, and the "plucks" function uses that to shove each possible element to the front of the list in order.
import List
breaks list = zip (inits list) (tails list)
plucks      = map (\(a,(b:bs)) -> (b:a++bs)) . filter (not.null.snd) . breaks

Once we have plucks, the recursive permutation generator is (almost) a one-liner:
lexPerm [] = [[]]
lexPerm list = concatMap (\(a:as) -> map (a:) $ lexPerm as) $ plucks list

nthLexPermNaive list n = (lexPerm list) !! n

(With "nth" counting from 0, of course.) For purposes of the problem at hand, this is plenty fast enough: I'm supposed to solve the problem in a minute, and I can get the millionth permutation in 10 seconds on my Mac. But 10 seconds is on the order of 10 billion operations with today's computers, which makes that pretty cheesy in the absolute sense, so I took a walk to grab some coffee and thought about it.

Of course we don't have to create the Library of Babel; we just want to index it. (Literally) exponentially better is, rather than generating all the permutations before the one we want, counting our way down to it:

facs              = scanl (*) 1 [1..]
nthLexPerm []   _ = []
nthLexPerm list n = (a : nthLexPerm as r) where                       
                       (q, r) = divMod n $ facs !! (length list - 1)
                       (a:as) = (plucks list) !! (fromIntegral q)

That is, we divide the permutations into buckets according to which list element goes first, count the size of the buckets with the factorial function, and figure out which bucket n is in; that tells us which list element is first (or next), and then we do it again with the rest of the list.

Here any reasonable-sized problem is done in a quarter of a second, and we can find the Collapse )th permutation of the first paragraph of Moby-Dick in two seconds.

(If we wanted to permute the whole text of Moby-Dick, this might run into trouble: in the process of figuring out the first letter, we have to spend at least quadratic time computing the factorial of the length of the remaining part of the list. For the earlier permutations, we could trim this down a bit by doing the factorial mod n.)

This entry was originally posted at http://adb.dreamwidth.org/1238.html. Please comment there using OpenID.