13

数値をシーケンスの一意の順列にマップできるアルゴリズムを探しています。同様の質問Fast permutation -> number -> permutation mapping algorithmのおかげで、Lehmer コードと階乗数システムについて知りましたが、その質問はシーケンスに重複する要素がある場合を扱っていません。

たとえば、「AAABBC」というシーケンスを考えてみましょう。6つあります！= 720通りありますが、6通りしかないと思います! / (3! * 2! * 1!) = このシーケンスの 60 の一意の順列。これらの場合、数値を順列にマップするにはどうすればよいですか?

編集: 「セット」という用語を「シーケンス」に変更しました。

4

5 に答える 5

9

順列から数へ:

K を文字クラスの数とします (例: AAABBC には 3 つの文字クラスがあります)。

N[K] を各文字クラスの要素数とします。(例: AAABBC の場合、N[K]=[3,2,1]、N= sum(N[K]) とします)

シーケンスのすべての正当な順列は、不完全な K-way ツリー内のパスに一意に対応します。

次に、順列の一意の番号は、K-ary ツリーターミナル ノードのポストオーダー トラバーサルにおけるツリー ノードのインデックスに対応します。

幸いなことに、実際にツリー トラバーサルを実行する必要はありません。ツリー内のターミナル ノードの数が辞書式に自分のノードより少ないことを知る必要があるだけです。ツリー内の任意のノードで、現在のノードの下にあるターミナル ノードの数は、シーケンス内の未使用の要素を使用した順列の数に等しいため、これは非常に簡単に計算できます。階乗。

したがって、元の 6 文字と順列の最初の要素が 'B' であるとすると、5!/3!1!1! と判断します。= 'A' で始まる 20 個の要素なので、順列数は 20 より大きい必要があります。最初の文字が 'C' だった場合、5!/2!2!1! と計算できます。(A ではない) + 5!/3!1!1! (not 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) と 2 番目の '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!) がB1 位で、10 (=5!/3!/2!/0!) がC1 位です。

番号 0..29 は で始まるすべてのシーケンスにマッピングAされ、30..49 は で始まるシーケンスにマッピングされ、50..59 は で始まるBシーケンスにマッピングされCます。

シーケンスの次の場所に対して同じプロセスが繰り返されます。たとえば、で始まるシーケンスを取得する場合、B番号 0 (=30-30) .. 19 (=49-30) を構成 ( A×3、B×1、C×1）

于 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

結果の数値が 1 つの単語 (32 または 64 ビット整数など) に比較的簡単に収まると仮定すると、リンクされた記事の多くは依然として適用されます。変数ベースからのエンコードとデコードは同じままです。何が変わるかは、ベースがどのように変化するかです。

シーケンスの順列を作成している場合は、シンボルのバケットから (元のシーケンスから) 項目を選択し、それを最初に配置します。次に、シンボルのバケツから別のアイテムを選び、その最後に置きます。バケット内のシンボルがなくなるまで、最後にシンボルを選択して配置し続けます。

重要なのは、残りのシンボルのバケツから毎回どのアイテムを選択したかです。残りのシンボルの数は、順列を構築するときに計算できるため、記録する必要はありません。これは、選択自体ではなく、選択の結果です。

ここでの戦略は、選択したものを記録してから、選択するために残っているものの配列を提示することです. 次に、選択し、選択したインデックスを記録し (変数ベース メソッドを介してパックします)、選択するものがなくなるまで繰り返します。(並べ替えられたシーケンスを構築していたときと同じように。)

シンボルが重複している場合は、どちらを選択しても問題ないため、同じシンボルとして扱うことができます。違いは、まだ重複が残っているシンボルを選択した場合、次回から選択するバケット内のシンボルの数を減らさなかったことです。

これを明確にする表記法を採用しましょう。

バケツに残っている重複したシンボルをリストして選択する代わりに、バケツに残っているシンボルのc a b c a a数とともにそれらをリストします: c-2 a-3 b-1.

cリストから選択すると、バケットがリストに残っていることに注意してくださいc-1 a-3 b-1。つまり、次に何かを選ぶときは、3 つの選択肢があるということです。

しかし一方でb、リストから選択した場合、バケツはそこにc-2 a-3残っています. つまり、次に何かを選ぶとき、選択肢は 2 つしかありません。

置換されたシーケンスを再構築するとき、置換数を計算していたときと同じ方法でバケットを維持するだけです。

実装の詳細は簡単ではありませんが、標準のアルゴリズムを使えば簡単です。あなたをやじるかもしれない唯一のことは、バケツ内のシンボルが利用できなくなったときに何をすべきかということです.

バケットが (上記のように) ペアのリストで表されているとします。c-1 a-3 b-1そして、 を選択しますc。結果のバケットはc-0 a-3 b-1です。しかしc-0、もはや選択の余地がないため、リストには 3 つではなく 2 つのエントリのみを含める必要があります。リスト全体を 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 に答える