Code

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.
1
2
3
4
5
6
7
8
9
10
11
/* n is the number of elements, p is the set of elements */
int perm2num(int n, int *p){
    int num = 0, add = 1;  
    for (int i = n - 2; i >= 0; i--){
        for (int j = i + 1; j < n; j++) 
            if ( p[j] < p[i] ) 
                num += add;
        add *= (n - i);
    }
    return num; 
}

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
2
3
4
5
6
7
8
9
10
void num2perm(int n, int *p, int num){
    for (int i = n - 1; i >= 0; i--){
        p[i] = num % ( n - i );
        num /= (n - i);
    }
    for (int i = n - 1; i >= 0; i--)  
        for (int j = i - 1; j >= 0; j--)  
            if ( p[j] <= p[i] ) 
                p[i]++;
}

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）和本声明。

分享到