Permutations of a small feat: cantor

1. Brief introduction

Cantor expansion is a bijection of all permutations to a natural number, which is often used for space compression when building hash tables.

For example, in all permutations containing , we define the following bijection:

The essence of Cantor expansion is to calculate the order of the current arrangement in all arrangements from small to large. It can be seen from the above figure that the sequence is the smallest and the sequence is the largest.

The formula for Cantor's expansion is:

represents the number of permutations smaller than the current permutation, so the final answer we need is, which means the number of permutations smaller than the number of positions in the current permutation from the right side of the position, pay attention to the number from the leftTo the right are.

For example: Find the Cantor expansion of .The first digit is 1, and the right side of 1 is less than 1, so , note that it is not .Similarly, there are:

, ,, so end up with:

So 24th in all ascending permutations that contain !!!

2. Code implementation

#includeusing namespace std;//First calculate the factorial of 0~9 in advance, which is convenient for calculationint fac[10]={1,1,2,6,24,120,720,5040,40320,362880};//x=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!, note that i is from 1~n,no 0int Contor(char *a,int n) {int sum=0,small=0;for(int i=0;i>n>>a;cout<

Copy