PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Mathem. Funktion für Permutation


Marscel
2015-11-17, 19:35:36
Ich suche was, vermutlich eher trivial, aber unter meinen Suchbegriffen habe ich spontan nichts gefunden:

Ich habe alle natürlichen Zahlen von 1 bis n (Menge: N_n). Jetzt suche ich eine bijektive Funktion N_n -> N_n, die ich um einen selbstgewählten Offset/Schieber/Seed a beeinflussen kann, welche mir für jedes i aus N_n eine Zahl aus der nach außen zufällig wirkenden Permutation pi(a, N_n) zurückliefert.

Da gibt es sicher irgendeine gängige Funktion für, nehme ich an. Einfallen tut mir leider gerade nichts, was ich für zuverlässig erachte.

Paran
2015-11-17, 19:56:02
Wie "zufällig" muss es denn sein?

y = a*x (mod 10000)

Dein Offset a sollte tellerfremd sein. Somit ist die Inverse auch definiert.

Marscel
2015-11-17, 20:15:28
Wie "zufällig" muss es denn sein?

y = a*x (mod 10000)

Dein Offset a sollte tellerfremd sein. Somit ist die Inverse auch definiert.

Zufällig i.S.v., dass man nicht ohne weiteres erkennen kann, nach welchem Schema die Zahlen fallen, das performt nicht so gut. Außerdem brauche ich wohl die Abhängigkeit von n, und ein Zusammenhang zwischen a und n sollte ebenso nicht notwendig sein.

Marscel
2015-11-17, 20:17:28
Jetzt hätte ich einfach mal nach "bijective random number generator" googlen sollen. :ugly:

Marscel
2015-11-18, 01:25:00
Falls es irgendwen interessiert: Mein Zahlenbereich erstreckt sich auf bis zu 24 Bit, realistisch etwas weniger. Blockchiffres bieten sich da an, wobei die üblichen deutlich größere Blocksizes als 24 Bit verwenden.

Um entsprechend nicht zu häufig Ergebnisse jenseits des Wertebereichs trashen zu müssen, habe ich nun einen Feistelchiffre mit entsprechenden Keys gewählt. Für meinen Geschmack sieht das gut verteilt aus und reicht vollkommen.