Ich kenne einige Routinen, die wie folgt funktionieren:
X n + 1
(X , max)
Zum Beispiel etwas wie ein LCG-Generator:
X n + 1 <(a * X
+ c) mod m
In diesem Generator ist nicht genug Parametrierung vorhanden, um jede Sequenz zu erzeugen.
Traumfunktion:
X n + 1
, max, Permutationszahl)
Diese Routine, die durch einen Index in die Menge aller Permutationen parametrisiert wird, würde die nächste Zahl in der Sequenz zurückgeben. Die Reihenfolge kann beliebig groß sein (das Speichern des Arrays und die Verwendung von faktorischen Zahlen ist nicht praktikabel.
Ist das nicht der Fall, hat jemand Zeiger auf ähnliche Funktionen, die entweder zustandslos sind oder für beliebig viele 'max' einen konstanten Zustand haben, so dass sie eine gemischte Liste durchlaufen.
Es gibt n! Permutationen von n Elementen. Um zu speichern, welche Sie verwenden, benötigen Sie mindestens log (n!) / Log (2) Bits. Nach der Stirling-Approximation benötigt dies ungefähr n log (n) / log (2) Bits.
Das explizite Speichern eines Indexes erfordert log (n) / log (2) Bits. Das Speichern aller n, wie in einem Array von Indizes, dauert n-mal so viele oder wiederum n log (n) / log (2). Informationstheoretisch gibt es keinen besseren Weg, als die Permutation explizit zu speichern.
Mit anderen Worten, der Index, den Sie übergeben, welche Permutation in der Menge Sie wollen, nimmt den gleichen asymptotischen Speicherplatz wie nur die Permutation schreiben. Wenn Sie beispielsweise den Index der Permutation auf 32-Bit-Werte beschränken, können Sie nur Permutationen von bis zu 12 Elementen handhaben. 64-Bit-Indizes bringen nur bis zu 20 Elemente.
Da der Index den gleichen Platz einnimmt wie die Permutation, ändern Sie entweder Ihre Darstellung, um die Permutation direkt zu verwenden, oder akzeptieren Sie das Entpacken in ein Array der Größe N.
Von meiner Antwort auf eine andere Frage :
Es ist tatsächlich möglich, dies zu tun Raum proportional zur Anzahl von Elemente ausgewählt, anstatt die Größe des Sets, aus dem Sie auswählen, unabhängig davon, welcher Anteil der Gesamtmenge, die Sie auswählen. Sie machen dies durch Erzeugen eines Zufalls Permutation, dann aus ihm auswählen so:
Wählen Sie eine Blockchiffre aus, z. B. TEA oder XTEA. Benutze XOR falten um Reduziere die Blockgröße auf die kleinste Macht von zwei größer als der Satz du wählst aus. Verwende das Zufallsprinzip Seed als Schlüssel zur Chiffre. Zu erzeuge ein Element n in der Permutation, verschlüsseln n mit der Chiffre. Wenn die Ausgangsnummer nicht in ist Dein Set, verschlüssele das. Wiederhole bis Die Nummer befindet sich im Set. Auf Durchschnittlich müssen Sie weniger tun als zwei Verschlüsselungen pro generierter Nummer. Dies hat den zusätzlichen Vorteil, dass wenn Ihr Seed ist kryptographisch sicher, so ist deine gesamte Permutation.
Ich habe viel detaillierter darüber geschrieben hier .
Natürlich gibt es keine Garantie, dass jede Permutation erzeugt werden kann (und abhängig von Ihrer Blockgröße und Schlüsselgröße, die vielleicht nicht einmal möglich ist), aber die Permutationen, die Sie bekommen können, sind höchst zufällig (wenn sie nicht waren, es wäre keine gute Chiffre), und Sie können so viele davon haben, wie Sie wollen.
Ist es möglich, eine Reihe von Permutationen zu indizieren, ohne vorher das Ganze im Speicher zu berechnen und zu speichern? Ich habe so etwas schon einmal probiert und keine Lösung gefunden - ich denke, das ist unmöglich (im mathematischen Sinne).
Haftungsausschluss: Ich habe Ihre Frage vielleicht falsch verstanden ...
Code, der eine iterate Schnittstelle verwendet. Die Zeitkomplexität ist O (n ^ 2). Die Raumkomplexität hat einen Overhead von: Kopie von n (log n Bits), einer Iterationsvariablen (log n Bits), Verfolgung von ni (log n Bits), Kopie des aktuellen Wertes (log n Bits), Kopie von p (n log n Bits), Erzeugung des nächsten Wertes (log n Bits) und eines Bitsatzes benutzter Werte (n Bits). Sie können einen Overhead von n log n Bits nicht vermeiden. Zeitweise ist dies auch O (n ^ 2), um die Bits zu setzen. Dies kann etwas reduziert werden, aber auf Kosten eines dekorierten Baums, um die verwendeten Werte zu speichern.
Dies kann geändert werden, um beliebig genaue Ganzzahlen und Bitmengen zu verwenden, indem stattdessen Aufrufe an die entsprechenden Bibliotheken verwendet werden, und die obigen Grenzen beginnen tatsächlich zuzuschlagen, statt auf N = 8 begrenzt zu werden (ein int kann sein) das gleiche wie ein kurzer und so klein wie 16 Bits). 9! = 362880 & gt; 65536 = 2 ^ 16
%Vor%Tags und Links algorithm language-agnostic math random