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 sequencenums[0, ..., n - 1]
, and1 <= nums[i] <= n
, output the index ofnums
among all the permutations. - Given
n
and an indexidx
(which is in range of[0, n!)
), output the corresponding sequencenums
.
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 sequencenums[0, ..., n - 1]
, and1 <= 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 satisfiesi < j && nums[i] > nums[j]
. - This is similar to "LCOF 51. 数组中的逆序对".
- A "Reverse-Order-Pair" is a pair
Then there is a bijection ("双射" in Chinese) between indice and permutations.
That is to say, the index of nums
is:
It seems quite simple and naive