Before we introduce the Cantor Expansion, let me show you a problem.

Give a group of numbers, such as nums = [1, 2, 3], it will has 3! = 6 different permutations. And we sort it in lexicographical order, then each of these permutations will have an unique index. That is:

idx     sequence
 0   :  [1, 2, 3]
 1   :  [1, 3, 2]
 2   :  [2, 1, 3]
 3   :  [2, 3, 1]
 4   :  [3, 1, 2]
 5   :  [3, 2, 1]

Now, we have 2 problems:

• Given n, and a sequence nums[0, ..., n - 1], and 1 <= nums[i] <= n, output the index of numsamong all the permutations.
• Given n and an index idx (which is in range of [0, n!)), output the corresponding sequence nums.

Please note that each element in nums is distinct here. We will consider the case that elements are not unique in the "Follow Up" chapter.

And this is what Cantor Expansion want to solve.

Cantor Expansion

You can read Baidu baike, not good article, not good code, but good examples.

• Given n, and a sequence nums[0, ..., n - 1], and 1 <= nums[i] <= n.
• Let \(a_i\) denote the number of "Reverse-Order-Pairs" of nums[i].
  • A "Reverse-Order-Pair" is a pair <i, j> that satisfies i < j && nums[i] > nums[j] .
  • This is similar to "LCOF 51. 数组中的逆序对".

Then there is a bijection ("双射" in Chinese) between indice and permutations.

That is to say, the index of nums is:

\[\text{index} = a_0 \cdot (n-1)! + a_1 \cdot (n-2)! + \dots + a_{n-2}\cdot(1!) + a_{n-1} \cdot (0!) \]

It seems quite simple and naive