Diskussion:Permutation

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Permutation“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen, und unterschreibe deinen Beitrag bitte mit oder --~~~~.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Zum Archiv

Auf dieser Seite werden Abschnitte ab Überschriftebene 2 automatisch archiviert, die seit 30 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind.

Zykel oder Zyklus?

Einmal ist von Zykeln und der Zykelschreibweise die Rede und anderswo von Zyklen. Heißt es nun Zykeln oder Zyklen? Heißt es nun Zykel oder Zyklus? 91.67.215.217 01:06, 20. Mai 2008 (CEST)

Die Wörter "Zykel" oder "Zykelschreibweise"/"Zykeldarstellung"/"Zykelzerlegung" stehen in keinem Wörterbuch oder Lexikon, in dem ich nachgeschaut habe (Duden, Wahrig, Wortschatz Leipzig, canoo, Bronstein Taschenbuch der Mathematik, Handbuch der Mathematik), nur "Zyklus" und "Zyklen" sind überall verzeichnet, auch speziell in Bezug auf den Gebrauch in der Mathematik. Andererseits gibt es durchaus einige Fachbücher mit "Zykel...": [1], auch wenn sie (zumindest bei Google Books) in der Minderheit sind: [2]. --80.129.71.53 09:10, 19. Dez. 2008 (CET)

Sowohl Aigner als auch Beutelspacher benutzen die deutsche Sprache korrekt und sprechen in ihren (im Artikel schon zitierten) Standard-Lehrbüchern von "Zyklendarstellung". Ich hab das daher jetzt hier angepasst. --Graf Alge (Diskussion) 02:17, 30. Sep. 2018 (CEST)

n-te Permutation

Kann man effizient (Also mit logarithmischer oder konstanter Laufzeit) die n-te Permutation einer m-elementigen Menge (bzw. eines m-Tupels) berechnen? Ich komme irgendwie nur auf rekursive Algorithmen, die eine miese Laufzeit haben. :-( --RokerHRO 15:39, 2. Dez. 2008 (CET)

Die Frage ist, wie du die Permutationen aufzählst. Wenn du zum Beispiel (1,...,m) permutierst, kannst du zuerst m an die (n div (m-1)!). Stelle setzen, n durch (n mod (m-1)!) ersetzen, dann m-1 an die (n div (m-2)!). noch freie Stelle usw. --80.129.71.53 11:39, 19. Dez. 2008 (CET)

Man schreibt die Zahl $n$ als Zahl in einem fakultätsbasierten Zahlensystem, interpretiert diese dann als Inversionstafel oder Lehmer-Code und wandelt diesen Vektor dann in die zugehörige Permutation um. Das geht bei direkter Implementierung in $O(m^{2})$ Operationen und bei geschickter Implementierung sogar in $O(m\log m)$. In jedem Fall ist die Laufzeit unabhängig von $n$. Einiges dazu steht nun im Artikel Fehlstand, weitere Informationen in TAOCP Band 3. Viele Grüße, --Quartl (Diskussion) 11:30, 18. Mär. 2013 (CET)

Danke für die späte Antwort. Aber wie kann ich nun effizient(!) die o.g. Permutation ermitteln, ohne zig Divisionen erstmal für die fakultätsbasierte Zahlendarstellung aufzuwenden? Wie sähe die von dir genannte „geschickte Implementierung“ aus? --RokerHRO (Diskussion) 17:54, 18. Mär. 2013 (CET)

Für die fakultätsbasierte Darstellung braucht man lediglich $m-1$ Divisionen (mit Rest) und $m-1$ Multiplikationen für die Fakultäten. Nachdem eine $m$-stellige Permutation aus $m$ Zahlen besteht, muss man jede zumindest einmal anfassen und kommt so um eine bessere Laufzeit als $O(m)$ ohnehin nicht rum. Besser geht es pro Permutation nur, wenn man alle Permutationen aufzählen will oder lediglich von der $n$-ten Permutation auf die $(n+1)$-te schließen will. Dann gibt es Algorithmen, wie den en:Steinhaus–Johnson–Trotter algorithm, die sukzessive Nachbarvertauschungen verwenden und so pro Permutation mit (im Mittel) konstanter Laufzeit in $m$ arbeiten können. Viele Grüße, --Quartl (Diskussion) 18:52, 18. Mär. 2013 (CET)

Durchnummerierung immernoch unklar

Irgendwie hab ich es immernoch nicht verstanden, was genau man machen muss. Konkretes Beispiel: Aus den Permutationen der Zahlen von 1…16 – also alle von (1,2,3,…,14,15,16) bis (16,15,14,…,3,2,1) lexikographisch sortiert – habe ich die folgende Permutation vor mir liegen: (6,10,4,3,9,12,5,11,14,8,3,1,7,13,15,2). Die wievielte ist das nun und wie berechnet man das am einfachsten? --RokerHRO (Diskussion) 11:06, 19. Aug. 2015 (CEST)

Siehe Diskussion:Fehlstand#Und wie berechnet man nun diese Inversionstafel?. --Quartl (Diskussion) 11:08, 19. Aug. 2015 (CEST)

Einverstanden, lasst und dort weiterdiskutieren. :-) --RokerHRO (Diskussion) 11:33, 19. Aug. 2015 (CEST)

Permutation ohne Wiederholung bei n Zeichenmengen

Bei der Vertauschung von Zeichen in einem Zeichenvorrat (Permutation ohne Wiederholung) kann man die duale Schreibweise der "Tupelvertauschung" verwenden.

bsp.: 3 Zeichen (x,y,z)

1. Schritt 1 1 1 (xyz) 2. Schritt 1 0 1 (x und z werden vertauscht) 3. Schritt 1 1 0 (x und y werden vertauscht) 4. Schritt 0 1 1 (y und z werden vertauscht)

Man geht dabei immer von der Startkonstelation der Zeichen aus.

Will man nun eine Formel aufstellen, die die Menge der Vertauschungen für V (Zeichenvorrat) angibt, bietet sich für N als Menge der Permutationen ohne Wiederholung folgendes an:

N = (2 + sum(m+1)) - (2n + 1) n = 1; n -> +inf; m = 1; m <= n

bsp.: 2 + [2 + 3 + 4] - (2*3 + 1) = 4 (nicht signierter Beitrag von Georg Neubauer (Diskussion | Beiträge) 12:43, 2. Dez. 2014 (CET))

Permutation mit Wdh. vs. Kombination ohne Wdh.

... sind nach der Lektüre der beiden Artikel wohl identisch!? Ich denke, dazu sollte ein Verweis erstellt werden. Ronny Michel (Diskussion) 23:06, 25. Mär. 2015 (CET)

Diese Fälle sind nicht identisch:

• Permutation mit Wiederholung: ${\frac {n!}{k!}}$ Möglichkeiten
• Kombination ohne Wiederholung: ${\frac {n!}{k!(n-k)!}}$ Möglichkeiten

Häufig werden aber Permutationen ohne Wiederholung und Variationen aller Objekte ohne Wiederholung gleichgesetzt (wähle $k=n$). Für eine Übersicht und Begriffsabgrenzung siehe den Artikel Abzählende Kombinatorik und die Einzelartikel. --Quartl (Diskussion) 07:21, 26. Mär. 2015 (CET)

Sorry, aber wenn ich z.B. einen Fall in der Art habe habe, dass eine 20-köpfige Gruppe in eine 17- und eine 3-köpfige gespalten werden soll, dann sind doch Permutation mit Wiederholung und Kombination ohne Wiederholung identisch!? Und deine Angabe zur Permutation mit Wdh. ist falsch und stimmt mit dem von dir verlinkten Artikel nicht überein. Die Permutation mit Wdh. stimmt mit dem Multinomialkoeffizienten überein, und die angegebene Kombination ohne Wdh. (Binomialkoeffizient) ist ein Sonderfall des Multinomialkoeffizienten: Binomialkoeff.="Zweispaltung", Trinomialkoeff.="Dreispaltung", Multinomialkoeff.="Multispaltung". Ronny Michel (Diskussion) 20:08, 27. Mär. 2015 (CET)

Die allgemeine Formel für Permutationen mit Wiederholung ist

${\binom {n}{k_{1},\ldots ,k_{s}}}={\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}$

Dabei ist mein Beispiel von oben der Spezialfall $k_{2}=\ldots =k_{s}=1$ und dein Beispiel der Spezialfall $s=2$. Allgemein kann man nicht sagen, dass Permutationen mit Wiederholung und Kombinationen ohne Wiederholung das gleiche sind, nur eben im Sepzialfall $s=2$. Dann ist in der Tat der Binomialkoeffizient ein Sonderfall des Multinomialkoeffizienten. Grüße, --Quartl (Diskussion) 12:55, 28. Mär. 2015 (CET)

OK, alles klar:-) Wäre es nicht sinnvoll, zu diesem Sonderfall s=2 einen kleinen Verweis einzubauen?Ronny Michel (Diskussion) 20:13, 29. Mär. 2015 (CEST)

Im Kombination (Kombinatorik)#Kombination ohne Wiederholung wird dieser Zusammenhang angesprochen. In diesem Artikel wäre eigentlich Permutation#Permutation mit Wiederholung der richtige Abschnitt, aber ich weiß nicht, ob das an dieser Stelle zu weit führen würde. In Multinomialkoeffizient könnte durchaus klarer herausgestellt werden, dass man im Fall $s=2$ (dort $r=2$) den Binomialkoeffizient erhält. Grüße, --Quartl (Diskussion) 08:44, 30. Mär. 2015 (CEST)

Reverse Permutation

Der Artikel erwähnt reverse Permutationen und behauptet, dass dieser Prozess das Vorzeichen umkehrt, das stimmt jedoch nicht: Das Vorzeichen der reversen Permutation ist $(-1)^{n(n-1)/2}$ mal das ursprüngliche Vorzeichen. (nicht signierter Beitrag von 130.60.188.208 (Diskussion) 16:26, 15. Jul 2015 (CEST))

Ja, das war falsch im Artikel. Danke für den Hinweis. --Quartl (Diskussion) 16:57, 15. Jul. 2015 (CEST)

Längste Permutation

Gibt es eigentlich einen Namen für die längste Permutation $(1,2,\ldots ,n-1,n)\to (n,n-1,\ldots ,2,1)$? Die kommt z.B. in Bruhat-Zerlegung#Generische Matrizen vor und bestimmt noch in vielen anderen Zusammenhängen.--Pugo (Diskussion) 09:04, 27. Dez. 2016 (CET)

π

Auf π sollte verzichtet werden, da es leicht mit 'π' verwechselt werden kann. --2.247.253.49 20:40, 28. Okt. 2018 (CET)

Dahlienblüten

Ich finde das Foto von den Dahlienblüten überhaupt nicht passend, da es in meinen Augen für den Artikel in keinster Weise relevant ist, wenn man den Einfluss der Veränderungen der Farbkanäle auf ein Foto veranschaulicht. (nicht signierter Beitrag von 83.175.70.68 (Diskussion) 10:11, 1. Sep. 2019 (CEST))

Das sehe ich genauso. Werde es aus dem Artikel entfernen. --Graf Alge (Diskussion) 19:35, 20. Okt. 2019 (CEST)

+1 Danke. Gruß --Apraphul ^Disk _WP:SNZ 20:21, 20. Okt. 2019 (CEST)

Permutation in der Musik: Rhythmik

ie Permutation in der Musik ist nicht auf Fuge und Zwölftonmusik begrenzt. In der Rhythmik ist dies ein ganz wichtiges Thema. Man nehme eine rhythmische Figur, beginnend auf dem Taktanfang und verschiebe diese um jeweils eine Einheit, wobei sich das ganze im Kreis wiederholt, weil Permutation n Deckungsgleich mit der Ausgangslage ist. Das wird besonders dann interesssant, wenn die Taktlänge nicht durch die Länge der verschobenen rhythmischen Figur teilbar ist. Es fehlen mir im Moment geeignete Quellen, obwohl ich dies in verschiedensten Lehrbüchern gesehen und daraus erlernt habe.

Im folgenden eine rhythmische Figur (bestehend aus den Schlägen a, b, c und d) über einen Grundrhythmus (bestehend aus einfachen Zählzeiten / Vierteln 1, 2, 3 und 4 eines 4/4-Taktes) permutiert. Nach der dritten Permutation is die Ausgangslage / Basislage wieder erreicht

     Grundrhythmus
        Takt 1          Takt 2          Takt 3          Takt 4      Takt 5
   ├───────────────┼───────────────┼───────────────┼─────────────┼───────────>
    1   2   3   4   1   2   3   4   1   2   3   4   1   2   3   4   1   2  ...
    a   b c d   a   b c d   a   b c d   a   b c d   a   b c d   a   b c d  ... 
   ├───────────┼───────────┼───────────┼───────────┼───────────┼───────────┼─>
    Basislage    Permut. 1   Permut. 2   Permut. 3   Permut. 4
    zu permut.                                      ≙Basislage
    Rhythmus

Nächste Permutation

Algorithmus, der alle Permutationen der (paarweise unterscheidbaren) Elemente $s_{1}$ bis $s_{n}$ der Reihe nach erzeugt, wenn er iterativ angewandt wird:

1. suche das erste Element $s_{i}$, das kleiner als das davor ist ($s_{i-1}>s_{i}$), oder setze $i=n+1$, wenn $s_{1},\cdots ,s_{n}$ aufsteigend geordnet sind
2. wenn $i\leq n$, dann suche in $s_{1},\cdots ,s_{i-1}$ das zu $s_{i}$ nächstgrößere und vertausche es mit $s_{i}$
3. invertiere die Folge der Elemente $s_{1},\cdots ,s_{i-1}$

Er beginnt nach der letzten Permutation wieder von vorn, es ist also egal, mit welcher man beginnt, wenn man in beliebiger Reihenfolge alle erzeugen will.

Man kann ebenso in 1. das erste größere suchen, und in 2. entsprechend das dazu nächstkleinere. Auch kann man von hinten beginnen statt von vorn. Es ergeben sich vier Varianten des Algorithmus, die die Permutationen in unterschiedlicher Reihenfolge erzeugen. --Megatherium (Diskussion) 12:55, 15. Jun. 2021 (CEST)

Ich habe mal einen Hinweis auf Algorithmen eingefügt, die bereits eigene Artikel in de.wp besitzen. Auf en.wp gibtv es auch weit mehr Infos zu Algorithmen.--Kmhkmh (Diskussion) 23:04, 16. Jun. 2021 (CEST)