Permutationen auf Array-Indizes

Java-Forum Allgemeine Themen
1

(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 :confused:

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…

2

Sowas schreit eigentlich wirklich nach einer Factory oder einem Builder. Mal ein kühner Vorschlag bei minimaler Sachkenntnis:

Permutator perm = Permutator.builder().ascending().inverse().build();
int[] order = perm.computeDouble(ds);

Natürlich muss man sicherstellen, dass die gewünschte Kombination auch irgendwie “sinnvoll” ist.

Die Frage ist nur, ob man die Berechnung auch so modular gestalten kann (da man sonst hinter den Kulissen doch wieder auf Monstermethoden verweisen muss).

3

Nun, so direkt wie skizziert würde das wohl nur bedingt Sinn machen, aber natürlich würden einige „Verbesserungsschritte“ für die Monstermethoden würden zumindest in eine ähnliche Richtung gehen.

Das schwierigste/unschönste finde ich dabei das Konzept der Permutation an sich sauber abzubilden. So, wie die Mathematiker das hinschreiben, passt das einfach nicht so dazu, dass man einen array permutieren will, weil man da eigentlich immer die indizes permutiert. Wenn man fragt, was die „sortier-Permutation“ für

40.0, 20.0, 10.0, 30.0

sein soll, könnte man sagen:

3, 1, 0, 2

Weil das beschreibt, welchen index jedes Element nach der Sortierung hat.

Man könnte aber auch sagen:

2, 1, 3, 0

weil das beschreibt, welchen index das Element vor der Sortierung hatte, das dann an diesem Index steht. (Und dass man leicht mal Arrays für Tests hinschreibt, bei denen diese beiden Optionen gleich sind, hat mich mehr Zeit gekostet, als ich zuzugeben bereit bin :roll_eyes: ).

Aber eigentlich ist die „sortier-Permutation“ das hier:

40.0, 20.0, 10.0, 30.0
  |     |     |     |
  v     v     v     v
10.0, 20.0, 30.0, 40.0

Und das macht für array ja nun mal gar keinen Sinn :slightly_frowning_face: Darum wird da wohl oft von einer „Index-Permutation“ die Rede sein müssen…

Der Charme der zweiten Option wäre eben, dass man das schön funktional und eigentlich ohne einen weiteren Array schreiben könnte:

IntToDoubleFunction f = { 40.0, 20.0, 10.0, 30.0 }
IntUnaryOperator p = { 2, 1, 3, 0 }

 // Das ergibt { 10.0, 20.0, 30.0, 40.0 } ;
IntToDoubleFunction result = i -> f.applyAsDouble(p.applyAsInt(i));

Aber das ist leider genau das Inverse von dem, was eine „Index-Permutation“ eigentlich wäre…

4

Wäre nicht eine Zyklendarstellung effizienter, wenn Teile des Arrays gar nicht permutiert werden?

Also z.B. die Sortierung von 40, 30, 20, 70, 50, 60, 10 dargestelt als [[0, 3, 6], [1, 2]]

5

Effizienz (im Sinne von geringerem Speicherbedarf) ist erstmal nicht das Kriterium. Das ganze ist schon kompliziert genug, wenn man einen Array hat, wo man „durch Draufschauen weiß, was er macht“ (wenn man weiß, welcher der beiden oben beschriebenen Fälle damit abgebildet wird :roll_eyes: ). Das ganze dann irgendwann kompakter zu repräsentieren, wäre ein Implementierungsdetail.

(Auch weiteres, wie ob ein interface IntPermutation extends IntUnaryOperator { int getSize() } sinnvoll ist, würde ich mir überlegen, wenn die theoretischen Fragen geklärt sind. Einschließlich des nächtelangen Grübelns über der Frage, ob der Name IntPermutation denn nicht durch IntSequence ersetzt werden sollte … )