Cantor Expansion is simple, however, for permutations with duplicate elements, some factors are changed.

For why I use English: Since I am going to write an English paper, I want to write several articles in English here for practice. Please forgive me for any inconvenience I may have caused to you.

# Basic Cantor Expansion

## Cantor Expansion

- A permutation without duplicate elements can have a mapping with a sequence [1..n], for example, think about
`2134`

, a permutation of {1, 2, 3, 4}. To calculate the position of`2134`

in all permutations of {1, 2, 3, 4}, we can follow the steps:`Pos = 1 * 3! + 0 * 2! + 0 * 1! = 6`

. The explanation is, since there’s only one element`1`

in elements behind`2`

and smaller than`2`

, if we swap`1`

and`2`

, there will be`3!`

permutations smaller than`2134`

. Similiar to this, no elements smaller than`1`

,`3`

and`4`

. So the related number with`2134`

is 6. In`C++`

, we can define a function named`perm2num`

, generate the position of a given permutation.

1 | /* n is the number of elements, p is the set of elements */ |

## Cantor Inverse

- To generate a permutation from the position it stays in, we can follow a reverse of the upper step. The
`C++`

code is just the reverse operation of`perm2num`

.

1 | void num2perm(int n, int *p, int num){ |

# With Duplicate Elements

- To generate the position of a permutation with duplicate elements, two factors influenced.
**First**, when calculate the possible increase for element`p[i]`

, in basic cantor expansion, we need to find how many elements are smaller than`p[i]`

and behind`p[i]`

, and multiply this number with`(n - i)!`

. Now, we need to divide this by the product of some factorials, which are how many elements are duplicate behind`p[i]`

. For example,`BABA`

, to calculate the increase for first B, 2 elements, both are A, are smaller than B. In basic Cantor Expansion, it should be`2 * 3!`

, now we need to divide it by`2! * 1!`

. The`2!`

is from 2 B after swapping, and`1!`

if from one A after swapping.**Second**, if one element`y`

has been used in calculating an increase for element`p[i]`

,`y`

should only be counted once. For example,`BABA`

only adds`2 * 3! / 2!`

once.

I want to recommand a website https://www.codewars.com here. My username in that website is Forec, you can find me here. I was inspired by one kata in that website, and that reminds me of cantor expansion. You can find the kata here. I didn’t find any articles talking about duplicate condition. I wish this can help you.

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2016/09/27/duplicate-cantor/) 、作者信息（Forec）和本声明。