13

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

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

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

4

5 回答 5

9

从排列到数字：

设 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') 留下 9。然后我们可以减去 'B' (6) 和第二个 'B'(3)，重新生成我们原来的排列。

于 2013-01-17T07:55:25.410 回答
1

这是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) 映射到具有配置 ( 3 x A、1 x B、1 x C)

于 2013-01-16T14:11:24.473 回答
0

一个非常简单的算法来映射一个由 n 位组成的排列的数字是

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

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

于 2013-01-08T10:28:06.550 回答
0

假设得到的数字相对容易地适合一个单词（例如 32 或 64 位整数），那么链接文章的大部分内容仍然适用。可变基数的编码和解码保持不变。变化的是基数如何变化。

如果您正在创建序列的排列，则从符号桶中（从原始序列中）挑选一个项目并将其放在开头。然后你从你的符号桶中挑选出另一个项目并将它放在它的末尾。您将继续在最后挑选和放置符号，直到您的存储桶中的符号用完为止。

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

此处的策略是记录您选择的内容，然后呈现一系列可供选择的内容。然后选择，记录你选择的索引（通过变量基方法打包），然后重复，直到没有什么可以选择。（就像上面构建置换序列时一样。）

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

让我们采用一种表示法来说明这一点：

与其列出我们存储桶中留下的重复符号以供选择，c a b c a a我们将列出它们以及存储桶中仍有多少个符号：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. Butc-0不再是一种选择，因此您的列表应该只有两个条目，而不是三个。您可以将整个列表向下移动 1 导致a-3 b-1，但如果您的列表很长，这很昂贵。一个快速简单的解决方案：将存储桶的最后一个元素移动到已移除的位置并减小存储桶大小：c0 a-3 b-1变为b-1 a-3 <empty>或仅b-1 a-3.

请注意，我们可以执行上述操作，因为桶中符号的列出顺序无关紧要，只要我们对数字进行编码或解码时的方式相同即可。

于 2013-01-15T17:35:03.207 回答
0

由于我不确定 g bronner 答案中的代码（或我的理解），我在 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)
}

这确实会产生具有正确整数范围的排名

于 2018-05-18T06:53:09.443 回答