Was wäre eine platzsparende Datenstruktur für eine Menge von Zykeln einer Permutation der Menge {1,...,N}?

3 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Für die Permutation selbst brauchst Du ja schon n! verschiedene Zustände, also log₂(n!) Bits. Aus einem solchen Permutationsindex kannst Du dann alles (auch die Zyklen) mit konstantem Speicheraufwand berechnen.

  • Geht es nur darum, "möglichst platzeffizient" zu sein, ist das sicher die beste Lösung. Nur die Performance ist dabei halt unterirdisch.
  • In der Praxis wird man daher gern einen konstanten Speicherfaktor (<3) in Kauf nehmen und die Permutation f einfach als Array der Länge n halten. Dann ist die "Berechnung" von f(i) ein konstanter Speicherzugriff, und der k-te Zyklus kann immerhin in "nur" ·k Schritten gefunden werden.
  • Ist auch das noch zu langsam, speichert man die r Zyklen zusätzlich als Array der Länge r, das je einen Repräsentanten z enthält. Über den ganzen Zyklus kann man dann effizient via z, f(z), f(f(z)), ... iterieren.
  • Es bringt kaum Vorteile, jeden ganzen Zyklus zu speichern. Das wäre nur interessant, wenn man sehr oft wahlfrei auf den k-ten Wert des i-ten Zyklus zugreifen muss. Aber dann muss man seine Anforderung an die Speichereffizienz überdenken.
Woher ich das weiß: Berufserfahrung

Solche Fragestellungen lassen sich nur unter Zuhilfenahme von retrograden, extrapolierten Analysemethoden lösen, dabei kann die syntaktische Identität der potentiellen Kommunikationsproblematik unter Berücksichtigung der potentiellen Einflussfaktoren im Fragmentarismus derartig extrapoliert werden, dass die Mastoptose des kategorischen Imperativs weitestgehend minimiert wird.

und ich hab mich schon so über die schnelle Antwort gefreut...............

2

kek

0

Also ich muss sagen, bei der Notation werde ich nicht wirklich schlau. Wie willst du die Permutationen notieren?

So wie oben, vollständig, oder als Produkt von Zyklen, wie unten, also uneindeutig?

Ein Array mit Listen leuchtet mir jetzt irgendwie schon am ehesten ein.

 - (Schule, Sprache, Mathematik)

also wir hatten das letztes Semester wie unten gemacht, also denke mal einfach als Produkt von Zyklen, wie würdest du es dann genau machen?

0
@RealAutism

Dann kannst du ja ein Array vom Typ List<Integer> erstellen und die einzelnen Produkte in die Listen packen.

Hätte ich jetzt so gemacht.

Du kannst natürlich auch Listen von Listen machen, es kommt halt darauf an, was du schon weißt.

Wenn du schon weißt, wie viele Produkte es geben wird, dann nimm ein Array, sonst eine Liste.

Wenn du schon weißt, wie viele Zahlen in den Produkten stehen werden, dann nimm ein Array, sonst eine Liste.

1
@Ecaflip

Du meinst ein Array vom Typ Pointer auf List<Integer> oder,weil man braucht ja einen Pointer,der auf den Listenkopf mit Dummy Element zeigt,oder lässt man den Kopf in diesem Fall weg und zeigt sofort auf das erste element des jeweiligen Zykels,also a_i1 ?Der zugriff auf das Array Element an der Adresse i liefert dann den Anfang des Zykels a_i1....a_iki , richtig ?

0
@RealAutism

Also ich weiß nicht welche Programmiersprache du jetzt verwendest, oder ob es nur um die Theorie geht.

In der Theorie wäre das Array [(1,4,2),(3,6),(5)] für das Beispiel, wobei die Pointer dann [Pointer -> 1, Pointer -> 3, Pointer -> 5] wären, wobei ich mir da nicht so sicher bin, wie du das mit den Pointern meinst.

1
@Ecaflip

keine programmiersprache, wir verwenden nur pseudocode, der sich an den höheren Programmiersprachen orientiert wie C++,Java oder so. Die Array Einträge wären dann Zeiger auf Listenelemente,um genau zu sein. In deinem Beispiel wäre dann A[1] Zeiger auf 1, A[2] Zeiger auf die 3, A[3] Zeiger auf die 5 und einen kompletten Zykel erhält man dann immer, indem man einfach die jeweilige einfach verkettete Liste mithilfe des Zeigers bis zum Ende durchläuft.

0
@RealAutism

bzw. Adressen,sagen wir A[i] = pi, dann einfach dereferenzieren mit pi*.value (für den ersten int-Wert) und pi*.succ*.value(für zweiten Wert usw.) listenelemente sind ja structs mit

struct listelem {int value, listelem* succ}

0

Was möchtest Du wissen?