# Cantor Expansion With Duplicate Elements

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.

## 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.

# 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.