algorithm - 数字到包含重复项的序列的唯一排列映射

Question

我正在寻找一种可以将数字映射到序列的唯一排列的算法。由于类似的问题 Fast permutation -> number -> permutation mapping algorithms，我发现了 Lehmer 代码和阶乘数字系统，但该问题不涉及序列中存在重复元素的情况。

例如，采用序列“AAABBC”。有6个! = 720种排列方式，但我相信只有6种!/(3! * 2! * 1!) = 此序列的 60 个唯一排列。在这些情况下，如何将数字映射到排列？

编辑:将术语“集合”更改为“序列”。

Answer 1

从排列到数字:

令 K 为字符类的数量(例如:AAABBC 具有三个字符类)

令 N[K] 为每个字符类中的元素数。 (例如:对于 AAABBC，我们有 N[K]=[3,2,1]，让 N= sum(N[K])

序列的每个合法排列都唯一对应于不完整 K-way 树中的一条路径。

然后，排列的唯一编号对应于 K 叉树终端节点的后序遍历中树节点的索引。

幸运的是，我们实际上不必执行树遍历——我们只需要知道树中有多少终端节点按字典顺序小于我们的节点。这很容易计算，因为在树中的任何节点，当前节点下方的终端节点数等于使用序列中未使用元素的排列数，该序列具有封闭形式解是阶乘的简单乘法。

所以给定我们的 6 个原始字母，并且我们排列的第一个元素是 'B'，我们确定会有 5!/3!1!1! = 20 个以“A”开头的元素，因此我们的排列数必须大于 20。如果我们的第一个字母是“C”，我们可以将其计算为 5!/2!2!1! (不是 A)+ 5!/3!1!1! (不是 B)= 30+ 20，或者作为60(总计)- 5!/3!2!0! (C) = 50

使用它，我们可以进行排列(例如“BAABCA”)并执行以下计算:排列 #= (5!/2!2!1!) ('B') + 0('A') + 0('A')+ 3!/1!1!1! ('B') + 2!/1!

= 30 + 3 +2 = 35

检查这是否有效:CBBAAA 对应于

(5!/2!2!1!(不是 A)+ 5!/3!1!1!(不是 B)) 'C'+ 4!/2!2!0! (不是 A)'B' + 3!/2!1!0! (不是 A)'B' = (30 + 20) +6 + 3 = 59

同样，AAABBC =0 ('A') + 0 'A' + '0' A' + 0 'B' + 0 'B' + 0 'C = 0

示例实现:

import math
import copy
from operator import mul

def computePermutationNumber(inPerm, inCharClasses):
    permutation=copy.copy(inPerm)
    charClasses=copy.copy(inCharClasses)

    n=len(permutation)
    permNumber=0
    for i,x in enumerate(permutation):
        for j in xrange(x):
            if( charClasses[j]>0):
                charClasses[j]-=1
                permNumber+=multiFactorial(n-i-1, charClasses)
                charClasses[j]+=1
        if charClasses[x]>0:
            charClasses[x]-=1
    return permNumber

def multiFactorial(n, charClasses):
    val= math.factorial(n)/ reduce(mul, (map(lambda x: math.factorial(x), charClasses)))
    return val

从数字到排列:这个过程可以反向完成，但我不确定效率如何:给定一个排列数和生成它的字母表，递归地减去小于或等于剩余排列数的最大节点数。

例如给定排列数 59，我们首先可以减去 30 + 20 = 50 ('C') 留下 9。然后我们可以减去 'B' (6) 和第二个 'B'(3)，重新生成我们的原始排列.