## July 15th, 2010

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

**( 2913-digit random numberCollapse )**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.