Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

[Delphi-Laie]

Zitat von mariusbenz:

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.

Schon bei 20, erst recht bei 60 Blöcken fällt brute force wegen der sehr stark wachsenden Fakultätsfunktion aus.

[Jumpy]

Zitat von Delphi-Laie:

Zitat von mariusbenz:

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.

Schon bei 20, erst recht bei 60 Blöcken fällt brute force wegen der sehr stark wachsenden Fakultätsfunktion aus.

Wahrscheinlich richtig, aber wenn man zunächst die Zahl der Permutationen pro Block auf die Interessanten reduziert, wie von Schokohase vorgeschlagen und dann die 60 Blöcke in z.B. 5er Pakete zerlegt, oder immer da eine Paketgrenze macht, wo zw. zwei Blöcken wegen komplett verschiedener Inhalte eh keine Optimierung möglich ist, und dann auf die Pakete die Brute-Force-Methode anwendet, könnte das was werden.
Nur wäre es dann eigentlich nicht mehr pur Brute Force .

[Delphi-Laie]

In meinem vorherigen Beitrage war ich unvollständig: Ich meinte natürlich, die Fakultätsfunktion wegen der Permutation(senumeration).

Soeben schaute ich mir Schokohases Beitrag eingehend an. Ich weiß nicht, was mit "stabil" gemeint ist. Stabil i.S. der Sortierung? Das ist eine beliebige Sortierung nicht per se, sondern es muß explizit ein stabiler Sortieralgorithmus gewählt werden! Diese "Sortierstabilität" war nach meiner Erinnerung in der Ausgangsproblemstellung nicht gefordert. Sie zu gewährleisten, ist jedoch mit der Wahl eines geeigneten, entsprechenden Sortieralgorithmus' leicht möglich.

Ja, und natürlich werden Blöcke bei diesen Permutationen als Elemente behandelt, d.h., daß innerhalb dieser Blöcke keinerlei Elementebewegungen stattfinden. Die Blöcke werden zeilenweise permutiert. Ist die Anzahl der Blöcke in der ersten Zeile a1, in der zweiten a2 usw. so dürfte die bei Brutforce abzuarbeitenden Gesamanzahl maximal a1!*a2!*... betragen. Das kann schnell heftig werden.

[Schokohase]

@Delphi-Laie

Ein Sortieralgorithmus (egal welcher) sollte egal wie immer so ein Ergebnis raushauen

Code:

aaabbbcccdddeee

sonst ist es kein Sortieralgorithmus. Einen echten stabilen Sortieralgorithmus braucht man hier gar nicht, weil es hier in diesem Anwendungsfall doch völlig egal ist, ob

Code:

aaabbbcccdddeee

oder

Code:

aaabbbcccdddeee

bei der Sortierung herauskommt.

(Wie, sie haben den Unterschied nicht bemerkt? Doch, sehen sie genau hin, das 2. a war vorher das 1. a also nicht stabil)

Oder anders gesagt, brauchen wir eigentlich keinen Sortieralgorithmus, sondern einen stabilen Gruppierungsalgorithmus, der gleiche Zeichen immer auf die gleiche Art zusammenfasst.