数字到包含重复项的序列的唯一置换映射 [英] number to unique permutation mapping of a sequence containing duplicates

问题描述

我正在寻找一种可以将数字映射到序列的唯一排列的算法.通过类似的问题快速排列，我找到了有关雷默代码和阶乘数系统的信息. ->数字->排列映射算法，但是这个问题不解决序列中存在重复元素的情况.

I am looking for an algorithm that can map a number to a unique permutation of a sequence. I have found out about Lehmer codes and the factorial number system thanks to a similar question, Fast permutation -> number -> permutation mapping algorithms, but that question doesn't deal with the case where there are duplicate elements in the sequence.

例如，采用序列"AAABBC".有6个！ =可以安排720种方式，但我相信只有6种！ /(3！* 2！* 1！)=此序列的60个唯一排列.在这种情况下如何将数字映射到排列?

For example, take the sequence 'AAABBC'. There are 6! = 720 ways that could be arranged, but I believe there are only 6! / (3! * 2! * 1!) = 60 unique permutation of this sequence. How can I map a number to a permutation in these cases?

将术语集合"更改为序列".

changed the term 'set' to 'sequence'.

推荐答案

从排列到数字:

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

Let K be the number of character classes (example: AAABBC has three character classes)

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

Let N[K] be the number of elements in each character class. (example: for AAABBC, we have N[K]=[3,2,1], and let N= sum(N[K])

该序列的每个合法排列都唯一地对应于一个不完整的K向树中的路径.

Every legal permutation of the sequence then uniquely corresponds to a path in an incomplete K-way tree.

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

The unique number of the permutation then corresponds to the index of the tree-node in a post-order traversal of the K-ary tree terminal nodes.

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

Luckily, we don't actually have to perform the tree traversal -- we just need to know how many terminal nodes in the tree are lexicographically less than our node. This is very easy to compute, as at any node in the tree, the number terminal nodes below the current node is equal to the number of permutations using the unused elements in the sequence, which has a closed form solution that is a simple multiplication of factorials.

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

So given our 6 original letters, and the first element of our permutation is a 'B', we determine that there will be 5!/3!1!1! = 20 elements that started with 'A', so our permutation number has to be greater than 20. Had our first letter been a 'C', we could have calculated it as 5!/2!2!1! (not A) + 5!/3!1!1! (not B) = 30+ 20, or alternatively as 60 (total) - 5!/3!2!0! (C) = 50

使用此方法，我们可以进行排列(例如'BAABCA')并执行以下计算: 置换#=(5！/2！2！1！)('B')+ 0('A')+ 0('A')+ 3！/1！1！1！ ('B')+ 2！/1！

Using this, we can take a permutation (e.g. 'BAABCA') and perform the following computations: Permuation #= (5!/2!2!1!) ('B') + 0('A') + 0('A')+ 3!/1!1!1! ('B') + 2!/1!

= 30 + 3 +2 = 35

= 30 + 3 +2 = 35

检查是否有效:CBBAAA对应

Checking that this works: CBBAAA corresponds to

(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

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

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

Likewise, 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

从数字到排列: 虽然我不确定效率如何，但可以反向执行此过程: 给定一个排列号及其生成的字母，递归地减去小于或等于剩余排列号的最大节点数.

From Number to Permutation: This process can be done in reverse, though I'm not sure how efficiently: Given a permutation number, and the alphabet that it was generated from, recursively subtract the largest number of nodes less than or equal to the remaining permutation number.

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

E.g. Given a permutation number of 59, we first can subtract 30 + 20 = 50 ('C') leaving 9. Then we can subtract 'B' (6) and a second 'B'(3), re-generating our original permutation.

这篇关于数字到包含重复项的序列的唯一置换映射的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！