Algorithm for finding numerical permutation given lexicographic index

Question

I am looking for an algorithm that given a set of numbers (for example 1 2 3) and an index (for example 2) will get me the second permutation of those numbers according to a lexicographic order. For example in this case the algorithm will return 1 3 2.

Answer 1

Here is a sample solution in Scala, which I will explain in detail:

/**
    example: index:=15, list:=(1, 2, 3, 4)
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
  if (list.isEmpty) list else {
    val len = list.size     // len = 4
    val max = fac (len)     // max = 24
    val divisor = max / len // divisor = 6
    val i = index / divisor // i = 2
    val el = list (i)
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }

Since Scala isn't that well known, I think I have to explain the last line of the algorithm, which is, apart from that, pretty self explanatory.

    el :: elist

constructs a new list from an element el and an list elist. Elist is a recursive call.

    list.filter (_ != el)

is just the list without the element el.

Test it exhaustively with a small List:

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n")

Test the speed of a bigger List with 2 examples:

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3)

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)

The result appears immediately on a 5 years old laptop. There are 479 001 600 permutations for a List of 12 elements, but with 100 or 1000 elements, this solution should still work fast - you just would need to use BigInt as Index.

How does it work? I made a graphic, to visualize the example, a List of (1, 2, 3, 4) and an index of 15:

A List of 4 Elements produces 4! permutations (=24). We choose an arbitrary index from 0 to 4!-1, let's say 15.

We can visualize all permutations in a tree, with the first node from 1..4. We divide 4! by 4 and see, that every first-node leads to 6 subtrees. If we divide our index 15 by 6, the result is 2, and the value in our zero-based List with index 2 is 3. So the first Node is 3, and the rest of our List is (1, 2, 4). Here is a table, showing how 15 leads to the element with index 2 in the Array/List/whatever:

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23
     0      |     1    |         2         |     3
            |          | 0  1  2  3  4  5  |

We now subtract 12, the first element of the cell (12...17) for the last 3 elements, which have 6 possible permutations, and see, how 15 maps to 3. Number 3 leads to the array index 1 now, which was element 2, so the result so far is List (3, 2, ...).

                        | 0 1 | 2 3 | 4 5 |
                        |  0  |  1  |  3  |
                              | 0 1 |

Again, we subtract 2, and end in 2 remaining elements with 2 permutations, and index (0, 3), mapping to the values (1, 4). We see, that the second element, belonging to the 15 from top, maps to value 3, and the remaining element for the last step is the other one:

                             | 0 | 1 |
                             | 0 | 3 |
                             | 3 | 0 |

Our result is List(3, 2, 4, 1) or the indexes (2, 1, 3, 0). Testing all indexes in order shows, that they yield all permutations in order.