Ein Array so richtig gut mischen
-
Hallo
Ich hab mal ne kleine Herausforderung für alle:
Ich suche eine Möglichkeit, ein Array zu mischen,
und wieder zurück zu sortieren -- mit Hilfe der
Mathematik.Also ein Array so richtig gut durchwürfeln, aber
halt berechenbar -- um es wieder zurück zu bekommen.
Folgendes Szenario:
Ich habe ein Array, dass gemischt werden soll. Danach
wird es auf die Festplatte geschrieben. Nun soll es
irgendwann wieder geladen werden, und in seinen originalen
Zustand zurück finden...Das muss alles gehen, ohne ein extra Array auf die Festplatte
zu schreiben!Infos:
Zur Verfügung steht: Das Eingabearray in der Form int[] mit
sehr vielen Einträgen... geht in die Millionen.
Dann ein Array mit festen Werten (byte[]). Das ist etwa 20
Einträge lang. Dieses Array muss auch benutzt werden.
Es kann auch später noch eindeutig einem großen Array zugeordnet
werden.Das war es. Damit muss man auskommen. Man kann natürlich
alle normalen mathematischen Funktionen benutzen, wie cos,
sin, exp und so weiter...Bedingungen:
Es sollte in endlicher Zeit zum Ergebnis führen.
Also sagen wir
mal bis zu einer Sekunde für eine Millionen Einträge im Hauptarray!
So in der Art... darf also keine Minuten dauern...Das Hauptarray soll aber nicht nur einfach um x Einträge
verschoben werden. Also jeden Eintrag um x Positionen verschieben.
Das ist zu einfach!Und die Arrays dürfen auch nicht vergrößert werden.
Meine eigene Idee:
Die beste Lösung geht wohl leider nicht:
Ich würde am liebsten alle Einträge im Hauptarray einfach nach dem
Wert sortieren. Die niedrigsten alle nach links, die höhsten weit nach
rechts.Das wäre die beste Lösung -- für mich!
Aber wie will man dann die Positionen der Werte rekonstruieren? Ja,
man braucht ein zweites Array, wo die Positionen drinne sind. Aber
wenn das Hauptarray 5 Millionen Einträge hat, muss man 10 Millionen
auf die Festplatte schreiben. Die Dateien werden mir einfach zu groß!
Mir fällt einfach nichts gutes ein
-
das erinnert mich an permutationen und symetriegruppen.
kurz: führt man eine permutation ( vertauschung ) von elementen durch, so kommt man nach n-maliger ausführung dieser permutation wieder zurück zur ursprüglichen anordnung.
auf
1 2 3
a b cwird die permutation 1->3 3->2 2->1 angewand =>
1 2 3
b c a
noch mal das gleiche:
1 2 3
c a b
noch mal:
1 2 3
a b c
= die urprügliche anordnung.edit: das heißt nich das das für beliebig große "felder" geht.. is nur ein denkanstoß.
IS ne gute frage ob das auch für beliebig große felder geht..?
-
Da ths die gleiche Frage auch auf www.javacore.de gestellt hat, gebe ich hier einfach mal den Link zu dem entsprechenden Thread an: