24 - Lexicographic Permutations

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?

Research

Permutations are what tuples is for. It would be very fortunate if tuples produces permutations lexicographically. Let's check.

≠ will give all permutations of rows from the array.

    ⧅≠3 ⇡3
╭─       
╷ 0 1 2  
  0 2 1  
  1 0 2  
  1 2 0  
  2 0 1  
  2 1 0  
        ╯

Nice!

Solution

Wowee trivial. We just adapt our parameters and get the millionth ordering. Remember that it is 1-indexed.

    ⊡ 999999 ⧅≠ 10 ⇡10
[2 7 8 3 9 1 5 4 6 0]

Great. Let's turn that into a number. We can take our pick from unbase,10 rev or parse reduce $"__"

    °⊥₁₀ ⇌ ⊡ 999999 ⧅≠ 10 ⇡10
2783915460

How fast?

Fast enough.

    ⊙◌⍜now(°⊥₁₀ ⇌ ⊡ 999999 ⧅≠ 10 ⇡10)
0.13539552688598633