22

以下で説明するタスクが理論的に可能かどうか、可能であればどうすればそれができるかを知りたいです。

要素の空間 (つまり、とNの間のすべての数字)が与えられます。その空間のすべての順列の空間を見て、それを と呼びましょう。の番目のメンバーは、 をマークすることができ、辞書式番号 の順列です。0N-1SiSS[i]i

たとえば、Nが 3 の場合S、順列のリストは次のようになります。

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(もちろん、大きな を見るとN、このスペースは非常に大きくなりN!ます。正確には。)

さて、インデックス番号iで順列を取得する方法と、その逆の方法 (特定の順列の辞書式番号を取得する方法) を既に知っています。しかし、もっと良いものが必要です。

一部の順列は、それ自体が巨大になる可能性があります。たとえば、 を見ているとしN=10^20ます。(のサイズはS、(10^20)!スタック オーバーフローの質問でこれまでに言及した最大の数だと思います:)

そのスペースのランダムな順列だけを見ている場合、辞書式番号で各アイテムを計算することは言うまでもなく、ハードドライブにすべてを保存することができないほど大きくなります。私が欲しいのは、その順列でアイテムにアクセスし、各アイテムのインデックスも取得できるようにすることです。つまり、与えられNたi順列を指定するには、インデックス番号を受け取り、そのインデックスにある番号を見つける関数と、番号を受け取り、それがどのインデックスにあるかを見つける別の関数を用意します。でそれを行いたいO(1)ので、順列の各メンバーを保存または反復する必要はありません。

クレイジー、あなたは言いますか？不可能？そうかもしれません。しかし、次のことを考慮してください。AES のようなブロック暗号は、基本的に順列であり、上で概説したタスクをほぼ達成します。AES のブロック サイズは16 バイトNです。( のサイズは重要ではありませんが、驚異的な、または約であり、「スタック オーバーフローで言及された最大数」の最近の記録を上回っています :)256^1610^38S(256^16)!10^85070591730234615865843651857942052838

各 AES 暗号化キーは、 上の 1 つの順列を指定しN=256^16ます。その順列は、太陽系の原子よりも多くのメンバーを持っているため、コンピューターに完全に保存できませんでした. ただし、アイテムへのアクセスは許可されます。AES を使用してデータを暗号化することにより、データをブロックごとに調べ、ブロック ( のメンバーrange(N)) ごとに暗号化されたブロックを出力します。そのメンバーはrange(N)、順列の元のブロックのインデックス番号にあります。復号化するときは、逆のことを行っています (ブロックのインデックス番号を見つける) O(1)。

AES やその他のブロック暗号を使用する際の問題は、非常に具体的NなN.S[i]私が好きな順列。

サイズと順列番号O(1)を指定して、順列でアイテム アクセスを取得することは可能ですか? もしそうなら、どのように？Ni

(幸運にもここでコードの回答を得ることができれば、それらが Python で提供されることを感謝します。)

更新：

一部の人々は、置換数自体が非常に巨大であり、数を読み取るだけではタスクが実行不可能になるという悲しい事実を指摘しました。次に、私の質問を修正したいと思います:順列の辞書式番号の階乗表現へのアクセスが与えられた場合、O(できるだけ小さい)で順列の任意のアイテムを取得することは可能ですか?

4

5 に答える 5

5

これを行う秘訣は、「底階乗で数える」ことです。

134 = 1*10^2+3*10 + 4 と同じように、134 = 5! + 2 * 3! +2！=> 階乗表記の 10210 (1! を含め、0! を除外)。N! を表現したい場合は、N^2 基数の 10 桁が必要になります。(各階乗桁 N について、保持できる最大数は N です)。0 と呼ぶものについて少し混乱するかもしれませんが、この階乗表現はまさに順列の辞書式数です。

この洞察を使用して、オイラー問題 24 を手で解くことができます。だから私はここでそれをやります、そしてあなたはあなたの問題を解決する方法を見るでしょう. 0 ～ 9 の 100 万番目の順列が必要です。階乗表現では、1000000 => 26625122 を取ります。これを順列に変換するために、数字 0、1、2、3、4、5、6、7、8、9 を取り、最初の数は 2 です。は 3 番目 (0 の可能性あり) であるため、最初の数字として 2 を選択し、新しいリスト 0,1,3,4,5,6,7,8,9 を作成し、7 番目の数字を取得します。 8 など、2783915604 を取得します。

ただし、これは、辞書式の順序付けを 0 から開始することを前提としています。実際に 1 から開始する場合は、そこから 1 を引く必要があり、2783915460 になります。これは実際、0 ～ 9 の数字の百万回順列です。

明らかにこの手順を逆にすることができるため、辞書編集番号とそれが表す順列の間で簡単に前後に変換できます。

ここで何をしたいのか完全にはわかりませんが、上記の手順を理解することは役に立ちます。たとえば、辞書編集番号がハッシュテーブルのキーとして使用できる順序を表すことは明らかです。また、数字を左から右に比較して数字を並べ替えることができるため、数字を挿入したら、階乗を計算する必要はありません。

于 2014-05-12T10:56:10.020 に答える
2

編集：

質問を誤解していましたが、無駄ではありませんでした。私のアルゴリズムは、順列の辞書編集数の階乗表現は、順列自体とほぼ同じであることを理解させてくれました。実際、階乗表現の最初の桁は、対応する順列の最初の要素と同じです (スペースが 0 から N-1 までの数字で構成されていると仮定します)。これを知っていると、順列自体ではなくインデックスを格納する意味がありません。辞書式番号を順列に変換する方法については、以下をお読みください。Lehmer コードに関するこのウィキペディアのリンクも参照してください。

元の投稿:

S 空間には、最初のスロットを埋めることができる要素が N 個あります。つまり、(N-1) 個あります! 0 で始まる要素。したがって、i/(N-1)! が最初の要素です ('a' と呼びましょう)。0 で始まる S の部分集合は (N-1)! 要素。これらは集合 N{a} の可能な順列です。これで、2 番目の要素を取得できます: i(%((N-1)!)/(N-2)!) です。このプロセスを繰り返すと、順列が得られます。

逆も同様に簡単です。i=0 から始めます。順列の最後の 2 番目の要素を取得します。最後の 2 つの要素のセットを作成し、要素の位置 (0 番目の要素または 1 番目の要素) を見つけます。この位置を j と呼びます。次に i+=j*2! です。プロセスを繰り返します (最後の要素から開始することもできますが、常に可能性の 0 番目の要素になります)。

Javaっぽい疑似コード:

find_by_index(List N, int i){
    String str = "";
    for(int l = N.length-1; i >= 0; i--){
        int pos = i/fact(l);
        str += N.get(pos);
        N.remove(pos);
        i %= fact(l);
    }
    return str;
}

find_index(String str){
    OrderedList N;
    int i = 0;
    for(int l = str.length-1; l >= 0; l--){
        String item = str.charAt(l);
        int pos = N.add(item);
        i += pos*fact(str.length-l)
    }
    return i;
}

find_by_index は O(n) で実行する必要がありますが、N は事前に順序付けされていると仮定し、find_index は O(n*log(n)) (n は N スペースのサイズ) です。

于 2014-05-10T23:01:49.863 に答える
0

ウィキペディアでいくつかの調査を行った後、このアルゴリズムを設計しました。

def getPick(fact_num_list):
    """fact_num_list should be a list with the factorial number representation, 
    getPick will return a tuple"""
    result = [] #Desired pick
    #This will hold all the numbers pickable; not actually a set, but a list
    #instead
    inputset = range(len(fact_num_list)) 
    for fnl in fact_num_list:
        result.append(inputset[fnl])
        del inputset[fnl] #Make sure we can't pick the number again
    return tuple(result)

明らかに、すべての数値を「選択」する必要があるため、これは O(1) には達しません。forループを実行するため、すべての操作が O(1) であると仮定getPickすると、O(n) で実行されます。

基数 10 から階乗基数に変換する必要がある場合、これは補助関数です。

import math

def base10_baseFactorial(number):
    """Converts a base10 number into a factorial base number. Output is a list
    for better handle of units over 36! (after using all 0-9 and A-Z)"""
    loop = 1
    #Make sure n! <= number
    while math.factorial(loop) <= number:
        loop += 1
    result = []
    if not math.factorial(loop) == number:
        loop -= 1 #Prevent dividing over a smaller number than denominator
    while loop > 0:
        denominator = math.factorial(loop)
        number, rem = divmod(number, denominator)
        result.append(rem)
        loop -= 1
    result.append(0) #Don't forget to divide to 0! as well!
    return result

繰り返しますが、これは s のために O(n) で実行されwhileます。

すべてを合計すると、見つけることができる最適な時間はO(n)です。

PS: 私は英語を母国語としないので、スペルや言い回しに誤りがあるかもしれません。あらかじめお詫び申し上げます。何か回避できない場合はお知らせください。

于 2014-05-14T19:14:50.237 に答える
0

階乗形式で格納された順列の k 番目の項目にアクセスする正しいアルゴリズムはすべて、最初の k 桁を読み取る必要があります。これは、最初の k のうちの他の桁の値に関係なく、読み取られていない桁が 0 であるか、最大値を取るかによって違いが生じるためです。これが事実であることは、正規の正しいデコード プログラムを 2 つの並列実行でトレースすることによって確認できます。

たとえば、順列 1?0 の 3 桁目をデコードする場合、100 の場合、その桁は 0 であり、110 の場合、その桁は 2 です。

于 2014-05-15T20:53:56.203 に答える