排名和重复unranking排列

问题描述

我阅读的排列我感兴趣的排名/ unranking方法。

I'm reading about permutations and I'm interested in ranking/unranking methods.

从论文的摘要：

排名功能的排列上的N个符号分配一个唯一的  在区间[0整数，n！ - 1]〜上述n的！排列。相应的  unranking功能是逆：给定0到n之间的整数！ - 1，  该函数的值是有这个级别的置换。

我做了一个排名和unranking功能在C ++中使用next_permutation。但是，这是不实际的对于n> 8。我在找一个更快的方法和 factoradics 似乎颇为流行。但我不知道这是否也适用于重复。那么，什么是与重复排列/ unrank排列好办法？

I made a ranking and an unranking function in C++ using next_permutation. But this isn't practical for n>8. I'm looking for a faster method and factoradics seem to be quite popular.But I'm not sure if this also works with duplicates. So what would be a good way to rank/unrank permutations with duplicates?

推荐答案

的一种方法是进行排名和unrank指数的选择由同等数目的特定组，例如

One way is to rank and unrank the choice of indices by a particular group of equal numbers, e.g.,

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))

这篇关于排名和重复unranking排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！