Cantor expansion

Cantor expansion can be used to find a $1\sim n$ any permutation of the rankings.

# What is ranked ranking?

put $1\sim n$ All permutations of are sorted lexicographically, and the position of this permutation is its ranking.

# Time complexity?

Cantor expansion can be done in $O(n^2)$ Find the ranking of an arrangement within the complexity, which can be done when using tree array optimization $O(n\log n)$。

# How to achieve it?

Because the arrangement is in lexicographic order, the higher the number, the higher the priority. That is to say, if the numbers before a certain digit in the two arrangements are the same, then if this digit is not the same, they will be sorted by this digit.

For example $4$ arrangement,$[2,3,1,4]<[2,3,4,1]$, because in the $3$ bits appear different, then $[2,3,1,4]$ is ranked in $[2,3,4,1]$ front.

# Give a chestnut

we know long as $5$ arrangement $[2,5,3,4,1]$ greater than $1$ any permutation in which the first $1$ as the first $5$ The arrangement is $4!$ species. This is very easy to understand. But for the second place we $5$ In terms, it is greater than The first digit is the same as this one, and this digit is better than $5$ small All permutations. But what we should note is that this one is not only better than $5$ Small, it must satisfy that it does not appear before the current arrangement, otherwise the statistics will be repeated. Therefore this one is $1,3$ or $4$, the first one is $2$ All permutations of are smaller than it, the amount is $3\times 3!$。

According to this statistics, the answer is $1+4!+3\times 3!+2!+1=46$. Note that we are counting rankings, so the first $+1$。

Notice that every time we use How many numbers smaller than it are currently there that have not yet appeared?, here you can use a tree array to count the number of times a number smaller than it appears.

# Inverse Cantor expansion

Because the ranking and permutation of the permutation are in one-to-one correspondence, the Cantor expansion satisfies the bijection relationship and is reversible. It can be worked back through a process similar to the one above.

If we know the ranking of a permutation, we can deduce the permutation. because $4!$ is strictly greater than $3\times 3!+2\times 2!+1\times 1!$ , so it can be considered that the length is $5$ arrangement, ranking $x$ divide by $4!$ Rounding down is how many numbers are smaller than the first number in the array.

# Quoting the example expanded above

First let $46-1=45$，$45$ Represents how many arrangements are smaller than this arrangement.$\lfloor\frac {45}{4!}\rfloor=1$, there is a number smaller than it, so the first digit is $2$。

At this time, let the ranking be subtracted $1\times 4!$ get $21$，$\lfloor\frac {21}{3!}\rfloor=3$, there is $3$ If the number is smaller than it, remove the existing ones $2$, this one is $5$。

$21-3\times 3!=3$，$\lfloor\frac {3}{2!}\rfloor=1$, there is a number smaller than it, then this bit is $3$。

let $3-1\times 2!=1$, there is a number smaller than it, this digit is the second remaining digit,$4$, the remaining one is $1$. That is $[2,5,3,4,1]$。

In fact we get the form There are two numbers less than it This conclusion shows that it is the current $3$ Numbers that have not been selected can also be maintained using line segment trees. The time complexity is $O(n\log n)$。

/*
* The Cantor expansion is a bijection that is fully arranged into a natural number and is often used for space compression when constructing hash tables.
* The essence of Cantor expansion: calculate the ranking of the current arrangement in all the total arrangements from small to large, so it is reversible
* Enter a positive integer N, enter a certain permutation from 1 to N, and find the ranking position of this permutation in the total permutation.
* If the input N is 3, the total arrangement is 123 132 213 231 312 321
* Input permutation 2 1 3 , 2 1 3 ranks third among all permutations, and the Cantor expansion value is how many permutations there are before this permutation
*/
/*Example: Enter 5763214 and calculate its serial number
* ①ans = 0, tmp = 0, string length is 7
* ②The first number 5 enters the loop and traverses 7 6 3 2 1 4. Among them, there are three numbers 3 2 1 smaller than 5, so tmp = 3
* ③ans = ans + tmp * factorial[6] = 0 + 3 * 6!
* ④The second loop, start looking at the second number 7, tmp = 0
* ⑤Traverse 6 3 2 1 4. There are 6 3 2 1 4, a total of five numbers smaller than 7, so tmp = 5
* ⑥ans = ans + tmp * factorial[5] = 3 * 6! + 5 * 5!
* ⑦And so on......
*/
#include<iostream>
#include<string>
using namespace std;
int factorial[20];//Storage factorial, 0! 1! 2! 3! …………
void get_fac(string str)//Get factorial
{ int n = str.size();//You can also use .length, n is the number of input permutation digits, for example, 51342 is five digits, then five factorials are obtained here factorial[0] = factorial[1] = 1; // 0! and 1! All are 1 for (int i = 2; i < n; ++i) { factorial[i] = factorial[i - 1] * i; } return;
}
int cantor(string str)//Cantor expansion
{ int ans = 1;//Serial number, 12345... Cantor expansion is 0, and the result during calculation is 0. ans cannot be recorded (increased), but it counts as a serial number, so ans starts from 1 int len = str.size();//String length for (int i = 0; i < len; ++i) { int tmp = 0;//In the following loop, record the number of numbers that are smaller than the i-th digit. for (int j = i + 1; j < len; ++j)//Traverse the following numbers starting from the last bit of the i-th bit { if (str[i] > str[j]) ++tmp;//If the following digit is less than the i-th digit, it meets the requirements of Cantor expansion } ans += tmp * factorial[len - 1 - i];//Because the factorial array is 0! 1! 2! 3! ... So multiply from the back to the front, and then start the second loop of the outer loop, and tmp is reassigned to 0 /*Conform to Cantor expansion formula X = An * (n - 1)! + An-1 * (n - 2)! + … + A2 * 1! + A1 * 0! An is the number of numbers smaller than the number after the i-th digit. */ } return ans;
}
int main()
{ string str; cin >> str;//Input arrangement get_fac(str); cout << cantor(str) << endl; return 0;
}