具有重复项和约束的排名和取消排名排列

Question

我想对具有重复项且 3 (0,1,2) 个不同元素的排列进行排序和取消排序。还有 no 1 follows directly after a 2 和 no 2 follows directly after a 1。目前，我使用标准排名和非排名算法进行重复排列。我不知道如何扩展这些以仅支持上述排列。我需要更改什么？

提前致谢。

Answer 1

排名算法如下：

#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;
}

您还可以通过使用 trans 数组来修改约束。

一旦有了 cnt 数组，也可以很容易地实现排序算法。

具有重复项和约束的排名和取消排名排列

Rank and unrank permutations with duplicates and constraints

arrays

algorithm

math

permutation

ranking