Ich möchte wissen, ob die unten erläuterte Aufgabe überhaupt theoretisch möglich ist und wenn ja, wie ich es tun könnte.

Ihnen wird ein Raum von gegebenN Elemente (d. h. alle Zahlen zwischen0 undN-1.) Sehen wir uns den Raum aller Permutationen in diesem Raum an und nennen ihnS. Dasith mitglied vonS, die markiert werden könnenS[i]ist die Permutation mit der lexikografischen Zahli.

Zum Beispiel, wennN ist also 3S ist diese Liste von Permutationen:

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

(Natürlich, wenn man einen großen betrachtetNDieser Raum wird sehr groß,N! um genau zu sein.)

Jetzt weiß ich es schonwie man die Permutation durch ihre Indexnummer erhälti, und ich weiß bereits, wie man das Gegenteil macht (die lexikografische Nummer einer gegebenen Permutation erhalten.) Aber ich will etwas besseres.

Einige Permutationen können für sich genommen sehr groß sein. Zum Beispiel, wenn Sie suchenN=10^20. (Die Größe vonS wäre(10^20)! was meiner Meinung nach die größte Zahl ist, die ich jemals in einer Stapelüberlauf-Frage erwähnt habe :)

Wenn Sie sich nur eine zufällige Permutation in diesem Bereich ansehen, wäre sie so groß, dass Sie nicht in der Lage wären, das Ganze auf Ihrer Festplatte zu speichern, geschweige denn, jedes Element nach lexikografischer Nummer zu berechnen. Ich möchte, dass ich auf diese Permutation zugreifen und den Index jedes Elements abrufen kann. Das ist gegebenN undi Um eine Permutation anzugeben, müssen Sie eine Funktion haben, die eine Indexnummer annimmt und die Nummer findet, die sich in diesem Index befindet, und eine andere Funktion, die eine Nummer annimmt und findet, in welchem Index sie sich befindet. Ich möchte das machenO(1)Ich muss also nicht jedes Mitglied in der Permutation speichern oder iterieren.

Verrückt, sagst du? Unmöglich? Das könnte sein. Beachten Sie jedoch Folgendes: Eine Blockverschlüsselung wie AES ist im Wesentlichen eine Permutation und erfüllt fast die oben beschriebenen Aufgaben. AES hat eine Blockgröße von 16 BytesN ist256^16 welches ist um10^38. (Die Größe vonS, nicht dass es darauf ankommt, ist eine Staffelung(256^16)!oder in der Nähe10^85070591730234615865843651857942052838, was meinen jüngsten Rekord für die "größte auf Stack Overflow erwähnte Zahl" übertrifft :)

Jeder AES-Verschlüsselungsschlüssel gibt eine einzelne Permutation anN=256^16. Diese Permutation konnte nicht vollständig auf Ihrem Computer gespeichert werden, da es mehr Mitglieder als Atome im Sonnensystem gibt. Es ermöglicht Ihnen jedoch den Elementzugriff. Wenn Sie Daten mit AES verschlüsseln, sehen Sie sich die Daten Block für Block und für jeden Block (Mitglied vonrange(N)) Sie geben den verschlüsselten Block aus, von dem das Mitgliedrange(N) das ist in der Indexnummer des ursprünglichen Blocks in der Permutation. Und wenn Sie entschlüsseln, machen Sie das Gegenteil (Ermitteln der Indexnummer eines Blocks). Ich glaube, dies geschieht inO(1)Ich bin mir nicht sicher, aber auf jeden Fall ist es sehr schnell.

Das Problem bei der Verwendung von AES oder einer anderen Blockverschlüsselung besteht darin, dass Sie sich auf ganz bestimmte Funktionen beschränkenNund es fängt wahrscheinlich nur einen winzigen Bruchteil der möglichen Permutationen ein, während ich in der Lage sein möchte, irgendwelche zu verwendenN Ich mag es und greife auf beliebige Permutationen zuS[i] das mag ich.

Ist es möglich zu bekommenO(1) Elementzugriff auf eine Permutation, gegebene GrößeN und Permutationsnummeri? Wenn das so ist, wie?

(Wenn ich das Glück habe, hier Code-Antworten zu erhalten, würde ich mich freuen, wenn sie in Python sind.)

AKTUALISIEREN:

Einige Leute wiesen auf die traurige Tatsache hin, dass die Permutationszahl selbst so groß sein würde, dass das bloße Lesen der Zahl die Aufgabe nicht durchführbar machen würde. Dann möchte ich meine Frage überarbeiten:Zugriff auf diefaktoradische Darstellung Ist es möglich, von der lexikografischen Zahl einer Permutation ein beliebiges Element in der Permutation in O zu erhalten (so klein wie möglich)?