number到包含重复项的序列的唯一排列映射

Question

我正在寻找一种算法,可以将数字映射到序列的唯一排列.由于类似的问题,快速置换 - >数字 - >置换映射算法,我已经发现了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路树中的路径.

然后,置换的唯一编号对应于K-ary树终端节点的后序遍历中的树节点的索引.

幸运的是,我们实际上不必执行树遍历 - 我们只需要知道树中有多少终端节点在字典上比我们的节点少.这非常容易计算,因为在树中的任何节点处,当前节点下方的终端节点数等于使用序列中未使用元素的排列数,其具有封闭形式解决方案,其是简单的乘法阶乘.

因此,鉴于我们的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')并执行以下计算:Permuation#=(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'),然后我们可以减去'B'(6)和第二'B'(3),重新生成我们的原始数据.排列.