带重复的排列的排名和取消排名

小编典典

带重复的排列的排名和取消排名

algorithm

我正在阅读有关排列的信息，并且对排序/不排序方法感兴趣。

从论文摘要：

对n个符号进行排列的排序函数会在[0，n！-1]到每个n！排列。相应的取消排序函数为反函数：给定0到n之间的整数！-1，函数的值是具有该等级的排列。

我使用next_permutation在C ++中进行了排名和取消排名。但这对于n>
8不可行。我正在寻找一种更快的方法，而因子分析似乎很受欢迎。但是我不确定这是否也适用于重复项。那么对重复的排列进行排序/取消排序的一种好方法是什么？

阅读 281

2020-07-28

共1个答案

小编典典

一种方法是按一组特定的等号对索引的选择进行排名和取消排名，例如，

def choose(n, k):
    c = 1
    for f in xrange(1, k + 1):
        c = (c * (n - f + 1)) // f
    return c

def rank_choice(S):
    k = len(S)
    r = 0
    j = k - 1
    for n in S:
        for i in xrange(j, n):
            r += choose(i, j)
        j -= 1
    return r

def unrank_choice(k, r):
    S = []
    for j in xrange(k - 1, -1, -1):
        n = j
        while r >= choose(n, j):
            r -= choose(n, j)
            n += 1
        S.append(n)
    return S

def rank_perm(P):
    P = list(P)
    r = 0
    for n in xrange(max(P), -1, -1):
        S = []
        for i, p in enumerate(P):
            if p == n:
                S.append(i)
        S.reverse()
        for i in S:
            del P[i]
        r *= choose(len(P) + len(S), len(S))
        r += rank_choice(S)
    return r

def unrank_perm(M, r):
    P = []
    for n, m in enumerate(M):
        S = unrank_choice(m, r % choose(len(P) + m, m))
        r //= choose(len(P) + m, m)
        S.reverse()
        for i in S:
            P.insert(i, n)
    return tuple(P)

if __name__ == '__main__':
    for i in xrange(60):
        print rank_perm(unrank_perm([2, 3, 1], i))

2020-07-28