我在寻找一种算法，可以在许多映射到一个序列的独特排列。 我已经发现了莱默代码和阶乘数系统由于采用了类似的问题， 快速置换- >数字- >置换映射算法 ，但这个问题不会在有序列中重复的元素的情况下处理。
例如，取该序列“AAABBC”。 有6个！ = 720点的方式，可以安排，但我相信只有6个！ /（3！×2！* 1！）= 60独特该序列的置换。 我该如何映射一个数字在这些情况下置换？
编辑：改变了术语“设置”到“序列”。
Answer 1:
从置换为数字：
设K是字符类的数量（例如：AAABBC有三种字符）
让N [K]是在每一个字符类元素的数量。 （例如：AAABBC，我们有N [K] = [3,2,1]，让N =总和（N [K]）
该序列的每个合法的排列则唯一对应于一个不完整的K-路树的路径。
置换的唯一号然后对应于树节点的在K叉树的终端节点的一个后序遍历的索引。
幸运的是，我们实际上没有执行树的遍历-我们只需要知道树很多终端节点如何在字典式排序比我们少的节点。 这是很容易计算，如在树中的任何节点，当前节点下方的数字终端节点是等于使用该序列中的未使用的元件排列的数量，其中有一个封闭形式的解决方案，它是一个简单的乘法阶乘。
所以给了我们6页原始的信件，我们排列的第一个元素是“B”，我们确定会有5！/ 3！1！1！ =与“A”开始，所以我们的排列数目必须大于20有我们的第一个字母是一个“C” 20层的元件，我们可以计算出它作为5！/ 2！2！1！ （未A）+ 5！/ 3！1！1！ （未B）= 30 + 20，或备选地为60（总） - !!! 5/3 2 0！ （C）= 50
利用这一点，我们可以采取的置换（例如 'BAABCA'），并执行以下计算：（！！5/2 2 1）Permuation＃=（ '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”（3），重新生成-（6）和第二“B”提供了原始排列。
Answer 2:
这里是在Java中的算法由一个整数映射到序列枚举可能的序列。
public class Main {
private int[] counts = { 3, 2, 1 }; // 3 Symbols A, 2 Symbols B, 1 Symbol C
private int n = sum(counts);
public static void main(String[] args) {
new Main().enumerate();
}
private void enumerate() {
int s = size(counts);
for (int i = 0; i < s; ++i) {
String p = perm(i);
System.out.printf("%4d -> %s\n", i, p);
}
}
// calculates the total number of symbols still to be placed
private int sum(int[] counts) {
int n = 0;
for (int i = 0; i < counts.length; i++) {
n += counts[i];
}
return n;
}
// calculates the number of different sequences with the symbol configuration in counts
private int size(int[] counts) {
int res = 1;
int num = 0;
for (int pos = 0; pos < counts.length; pos++) {
for (int den = 1; den <= counts[pos]; den++) {
res *= ++num;
res /= den;
}
}
return res;
}
// maps the sequence number to a sequence
private String perm(int num) {
int[] counts = this.counts.clone();
StringBuilder sb = new StringBuilder(n);
for (int i = 0; i < n; ++i) {
int p = 0;
for (;;) {
while (counts[p] == 0) {
p++;
}
counts[p]--;
int c = size(counts);
if (c > num) {
sb.append((char) ('A' + p));
break;
}
counts[p]++;
num -= c;
p++;
}
}
return sb.toString();
}
}
由该算法所使用的映射如下。 我使用的问题给出的例子（3×A，2×B，1×C）来说明它。
有60个（= 6！/ 3！/ 2！/ 1！）在总的可能的序列，30（= 5！/ 2！/ 2！/ 1！）其中有一个A在首位，20（= 5！/ 3！/ 1！/ 1！）具有B在首位，和10（= 5！/ 3！/ 2！/ 0！）具有C在首位。
0..29被映射到开头的所有序列中的数字A ，30..49被映射到开始于序列B ，和50..59被映射到序列开始C 。
相同过程重复序列中的下一个位置，例如，如果我们取序列开始B我们现在必须映射数字0（= 30-30）.. 19（= 49-30），以与配置序列（3×A，1×B，1×C）
Answer 3:
一个非常简单的算法来映射一个编号为置换由n个数字是
number<-digit[0]*10^(n-1)+digit[1]*10^(n-2)+...+digit[n]*10^0
你可以找到大量的资源，为算法生成排列。 我猜你想在生物信息学使用这种算法。 例如，你可以使用和itertools.permutations在Python。
Answer 4:
假设得到的数目的字（例如，32位或64位整数）相对容易地内部配合，然后多链接的文章的仍然适用。 编码和解码从一个可变基保持不变。 什么样的变化是如何碱变化。
如果您要创建一个列的排序，你挑选出你的符号斗的项目（从原来的序列），并把它在开始。 然后你挑选出从符号的水桶另一个项目，并把它放在那结束。 你会在年底保持拾取和放置符号，直到你在你的水桶跑出来的符号。
什么是显著为您挑选出来的剩余符号的每次桶的哪个项目。 其余符号的数量是你不必记录，因为你可以计算出，当你建立了置换 - 这是你的选择，而不是自己选择的结果。
这里的战略是记录你选择什么，然后再呈现什么剩下的选择数组。 然后选择，你选择哪个索引（通过可变基数方法包装它）记录，并重复，直到什么都不剩选择。 （就像当你建设一个置换的序列以上。）
在重复的符号的情况下，不要紧，你挑哪一个，所以你可以把它们当作同一符号。 不同的是，当你拿起它仍然有重复的左标志，你并没有减少在桶符号的数量从下一次挑选。
让我们通过一个符号，它说明了这一点：
而不是列出留在我们的桶式两份符号可供选择，喜欢的cabcaa我们将用多少沿着列出他们仍然在斗： c-2 a-3 b-1
需要注意的是，如果你选择c从列表中，桶中有c-1 a-3 b-1左边它。 这意味着下一次我们捡东西，我们有三个选择。
但在另一方面，如果我选b从列表中，桶中有c-2 a-3左边它。 这意味着下一次我们捡东西，我们只有两个选择。
当重构置换的序列，我们只是保持斗的方式，当我们计算排列号码相同。
实施细节为不平凡的，但他们与标准算法简单。 可能你刁难的唯一事情是做什么的时候你斗的象征不再可用。
假设你的水桶是由对（如上）的列表表示： c-1 a-3 b-1和你选择c 。 您的所得桶是c-0 a-3 b-1 。 但c-0不再是一个选择，让您的列表应该只有两个条目，而不是三个。 您可以通过1导致移动整个列表中向下a-3 b-1但如果您的列表很长，这是昂贵的。 一种快速简单的解决方案：在桶的最后元件移动成移除的位置和降低你的桶大小： c0 a-3 b-1变为b-1 a-3 <empty>或只是b-1 a-3
需要注意的是我们能做到上面，因为它并不重要要想在桶中的符号列在，只要它以同样的方式，当我们编码或解码的数量。
Answer 5:
正如我不确定在克代码布朗纳的答案 （或我的理解），我重新编码它在R作为如下
ritpermz=function(n, parclass){
return(factorial(n) / prod(factorial(parclass)))}
rankum <- function(confg, parclass){
n=length(confg)
permdex=1
for (i in 1:(n-1)){
x=confg[i]
if (x > 1){
for (j in 1:(x-1)){
if(parclass[j] > 0){
parclass[j]=parclass[j]-1
permdex=permdex + ritpermz(n-i, parclass)
parclass[j]=parclass[j]+1}}}
parclass[x]=parclass[x]-1
}#}
return(permdex)
}
这确实产生的排序与整数的权利范围
文章来源: number to unique permutation mapping of a sequence containing duplicates
