(Abgetrennt von Frust-Thread - #1035 von Marco13)
Ich dachte eigentlich, Permutationen wären ~„einigermaßen einfach“ (auch wenn ich wußte, dass man da mit Symmetriegruppen, Zyklen & Co recht tief in den einen oder anderen Kaninchenbau abtauchen kann).
Aber vielleicht hat jemand ja eine kreative Idee: Ich bastle im Moment ein paar Klassen, wo man (z.B.) „sortier-Permutationen“ erstellen kann. Die Grundidee ist dabei, eine Sortierung nicht direkt durchzuführen, sondern nur die Permutation zu berechnen, die die Sortierung durchführt. Da war ein Zwischenstand eben sowas
double d[] = { 70, 50, 20, 10, 60, 30 };
int order[] = computeSortingPermutation(d);
was dann sowas ausgegeben hat wie
d = [70.0, 50.0, 20.0, 10.0, 60.0, 30.0]
order = [5, 3, 1, 0, 4, 2]
D.h. die order
besagt:
- Das Element mit index 0 steht steht nach der Sortierung an index 5
- Das Element mit index 1 steht steht nach der Sortierung an index 3
- …
Aber irgendwie hat’s mich dann immer wieder in der einen oder anderen Richtung aus der Kurve getragen, und mir dämmerte, dass das damit zu tun hat, dass das, was da ausgerechnet wird, ja keine Permutation ist, sondern eine „Permutation für die Indizes“.
Nach einigem hin und her und Websuchen bin ich dann über Permutations | Gowers's Weblog gestolpert, wo das ganze zerpflückt wird. (Überraschenderweise sind weder Wikipedia noch Wolfram noch Stackexchange da sooo klar wie ich es mir gewünscht hätte - siehe auch Do permutations apply to places or indices? - Mathematics Stack Exchange )
Im wesentlichen bedeutet das also: Die Permutation der Werte und die Permutation der Indizes sind (grob gesagt) invers zueinander.
Das hat den etwas unschönen Effekt, dass das
public static IntToDoubleFunction applyDoublePermutation(
IntToDoubleFunction input, IntUnaryOperator permutation) {
return i -> input.applyAsDouble(permutation.applyAsInt(i));
}
eben nicht so funktioniert, wie ich mir das zuerst gedacht hatte
Eigentlich fände ich es schön, das ganze mal sauber runterzumodellieren. Praktisch alles, was man findet, bezieht sich darauf, „Permutationen einer Liste“ zu erstellen (d.h. im wesentlichen das, was ich auch mal in Combinatorics/PermutationIterable.java at master · javagl/Combinatorics · GitHub hingepfuscht hatte). Aber nach dem Weg von
- computeSortingPermutation
- computeAscendingSortingPermutation
- computeAscendingDoubleSortingPermutation
- computeAscendingDoubleSortingIndexPermutation (!!! Index !!!)
- computeInverseAscendingDoubleSortingIndexPermutation
- …
muss ich wohl mal einen Schritt rückwärts machen, und nochmal mit leicht zusammengekniffenen Augen draufschauen: Moment, worum geht’s eigentlich?
Vermutlich könnte man das leichter sauberer modellieren, wenn man von vornherein ein paar der Freiheitsgrade im Blick (gehabt) hätte…