The Problem

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

   012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

The Solution

The first thing we need to do is write a function to generate permutations.

There are a number of approaches to this. I have yet to find one that I'm really happy with. Obviously, the more elements there are, the more permutations there are and the longer it takes to generate them.

The following function takes an array and returns all of its permutations. It uses a Set to keep track of which elements have been used as it recurses over the list of elements.

let getPermutations arr =

    let rec permutations list taken = 
        seq { 
            if Set.count taken = List.length list then
                yield [] 
            else 
                for l in list do
                    if not (Set.contains l taken) then 
                        for perm in permutations list (Set.add l taken) do
                            yield l::perm 
            }

    let lst = arr |> List.ofArray
    permutations lst Set.empty

Now we can generate permutations of the digits 0123456789.

let input = "0123456789" |> Array.ofSeq
let perms = 
    getPermutations input
    |> Seq.map (fun l -> System.String.Join("", l))
    |> Seq.sort

The above generates the permutations. There are 3,628,800 of them. Then it converts each permutation into a string and sorts them. Now we can find the answer.

#time
perms |> Seq.item 999999
#time

Since the position is 0-based, the one we want is element 999,999.

If you're like me, you probably noticed two possible optimizations here.

First: Is it strictly necessary to convert all items in the list to a string? Can't we sort it first and then only convert the item we need?

Yes, apparently we do. Even though F# is perfectly capable of comparing two arrays in the manner we need, this is apparently much slower than comparing strings. With the code as written, this executes in 11 seconds on my machine. If I move the string conversion to the end, the program exceeds the 1-minute time limit.

Second: Is that the fastest way to convert an array of digits back into a string? Yes, apparently it is. I have experimented with many different ways to do this (simple concatenation, StringBuilder, and others) and nothing really beats this.

Other Posts in This Series