arrays - Rank and unrank permutations with duplicates and constraints

Question

I want to rank and unrank permutations with duplicates and just 3 (0,1,2) different elements. Also no 1 follows directly after a 2 and no 2 follows directly after a 1. Currently I sit on the standard rank and unrank algorithmn for permutations with duplicates. I have no clue how to extend these to support only the above mentioned permutations. What do i have to change?

Thanks in advance.

Answer 1

Here is the ranking algorithm:

#include <vector>
#include <array>
#include <cassert>

// allowed transitions
// trans[i][j] is true iff j can follow directly after i
const bool trans[3][3] = {
    /*     0  1  2   */
    /*0*/ {1, 1, 1},
    /*1*/ {1, 1, 0},
    /*2*/ {1, 0, 1},
};

/// returns the rank of a given permutation
int rank(std::vector<int> perm) {
    // n is the size of the perm
    int n = perm.size();

    // using Dynamic Programming we are going to compute cnt[n][last]
    // cnt[n][last]: #permutations of length `n+1` starting with `last` 
    std::vector<std::array<int, 3>> cnt(n+1);

    // the base case
    cnt[0][0] = cnt[0][1] = cnt[0][2] = 1;
    
    // here we compute the cnt array
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            cnt[i][j] = 0;
            for (int k = 0; k < 3; k++) {
                if (trans[j][k]) {
                    cnt[i][j] += cnt[i-1][k];
                }
            }
        }
    }
    
    int rank = 0;
    
    // now we can compute the rank of perm using cnt
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < perm[i]; j++) {
            if (i == 0 || trans[perm[i-1]][j]) {
                // we calculate the count of all the permutations 
                // that are lexicographically smaller than perm.
                // cnt[n-i-1][j] is equal to the number of permutations
                // of length n that start with 
                // the prefix {perm[0], perm[1], ... perm[i-1], j}
                rank += cnt[n-i-1][j];
            }
        }
    }

    return rank;
}

int main() {

    assert( rank({0, 0}) == 0 );
    assert( rank({0, 1}) == 1 );
    assert( rank({0, 2}) == 2 );
    assert( rank({1, 0}) == 3 );
    assert( rank({1, 1}) == 4 );
    assert( rank({2, 0}) == 5 );
    assert( rank({2, 2}) == 6 );

    assert( rank({0, 0, 0, 0}) == 0 );
    assert( rank({0, 0, 2, 0}) == 5 );
    assert( rank({0, 1, 0, 1}) == 8 );
    assert( rank({0, 2, 0, 0}) == 12 );

    return 0;
}

You can also modify the constraints by playing with the trans array.

The unranking algorithm can also be easily implemented once you have the cnt array.