号码包含重复的序列的唯一排列映射

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-方式树。

置换的唯一编号，然后对应于该树的节点中的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'）并执行以下计算： 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 

从数量排列： 这个过程可以反过来做，虽然我不知道如何有效地： 鉴于一个置换数字和它从中产生的字母表，递归地减去小于或等于剩余置换数字的最大数量的节点。

E.g.给定59的置换数，我们首先可以从9减去30 + 20 = 50（'C'）。然后我们可以减去'B'（6）和第二个'B'（3），重新产生我们原来的置换。

Answer 2

一个很简单的算法映射置换一批由n个数字是

number<-digit[0]*10^(n-1)+digit[1]*10^(n-2)+...+digit[n]*10^0 

您可以找到大量资源的算法来生成排列。我想你想在生物信息学中使用这个算法。例如，你可以使用Python中的itertools.permutations。

Answer 3

假设结果数字比较容易适合单词（例如32或64位整数），那么大部分链接的文章仍然适用。来自可变基地的编码和解码保持不变。基地的变化有哪些变化。

如果您正在创建一个序列的排列，您可以从一大堆符号（从原始序列）中挑选一个项目并将其放在开头。然后你从一大堆符号中挑选出另一个项目，并将其放在最后。你会继续挑选和放置符号，直到你用完了桶中的符号。

什么是重要的是你每次从剩下的符号桶中挑出哪个项目。剩余符号的数量是您不必记录的，因为您可以在构建排列时计算 - 这是您选择的结果，而不是选择本身。

这里的策略是记录您选择的内容，然后展示剩下要选择的内容。然后选择，记录您选择的索引（通过变量基本方法打包），并重复，直到没有剩下可选项。 （就像上面你在构建排列序列时一样）。

在重复符号的情况下，选择哪一个并不重要，因此可以将它们视为相同的符号。不同之处在于，当你选择一个仍然有重复的符号时，你并没有减少下次选择的符号数量。

让我们通过一个符号，它说明了这一点：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 4

以下是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 x A，2 x B，1 x 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）映射到了数字0（= 30-30）...... 19（= 49-30）具有配置的序列（3×A，1×B，1×C）