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.

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

Zum Archiv

Automatische Archivierung

Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit 30 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. Das aktuelle Archiv befindet sich unter /Archiv.

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)

Taschenrechner abweichend

Taschenrechner rechnet mit der "nCr"-Taste die Kombinationen wie im entsprechenden Artikel – aber mit der "nPr"-Taste rechnet er weder n! noch n!/k! wie im Artikel angegeben, sondern n!/(n-k)!. Kann es sein, dass es evtl. (im Englischen) abweichende Definitionen gibt? --89.204.139.126 17:34, 31. Jan. 2023 (CET)

Wo steht das im Artikel? --Digamma (Diskussion) 22:01, 31. Jan. 2023 (CET)

Permutation#Permutation_mit_Wiederholung. Auch Wolfram rechnet (wie der Taschenrechner), z.B. nPr(10, 3)=720. Lt. Artikel würde man aber 10!/3! =604800 erwarten, oder? --46.114.196.210 22:54, 31. Jan. 2023 (CET)

Ich sehe da im Artikel kein "nPr". Das ist schlicht etwas anderes als Permutationen mit Wiederholungen. Mit "nPr" bestimmt man die Zahl der möglichen Ziehungen von r Elementen aus einer k-elementigen Menge ohne Zurücklegen und mit Berücksichtigung der Reihenfolge. --Digamma (Diskussion) 20:15, 2. Feb. 2023 (CET)

Interpretation der Permutation

Durch die Interpretation schleicht sich hier m.E. ein Fehler ein. Die Abbildung π wird so interpretiert, dass sie eine Zahl (also die Nummer des alten Platzes) auf die Nummer des neuen Platzes abbildet. Sie bildet also Plätze ab. Kann man so machen. Dann stimmt aber die Interpretation weiter unten im Abschnitt 'Permutationsmatrizen' nicht mehr: nämlich, dass durch die zugehörige Matrix "... die Elemente ... permutiert" werden. Die Elemente des Spaltenvektors würden nämlich gerade durch die transponierte Matrix, also der inversen Abbildung, permutiert. Die eigentliche Permutation wird also von π^{-1} bewerkstelligt. Vorschlag: die Interpretation wechseln, so dass π nicht Platznummern, sondern die Elemente selbst abbildet, also altes Element (=alter Platz) auf neues Element. Dann würde tatsächlich π die eigentliche Permutation sein. Egal wie rum: aber es sollten nicht Elemente auf Plätze, oder Plätze auf Elemente abgebildet werden, sondern immer nur auf die betrachtete Menge selbst. --ds --94.221.107.72 17:30, 4. Nov. 2023 (CET)

Auch die Interpretation altes Element auf neues Element, im Artikel im Abschnitt Definition "Anschaulich nimmt durch die Permutation jedes Element $x_{i}$ den Platz des ihm zugeordneten Elements $\pi (x_{i})$ ein", passt nicht. Diese Interpretation wurde nachträglich vor die bereits bestehenden Definitionen der Permutationsmatrix und der Komposition eingefügt (https://de.wiki.x.io/w/index.php?title=Permutation&diff=prev&oldid=113342292). Zur Permutationsmatrix siehe vorhergehenden Beitrag, zur Komposition siehe das zugehörige Beispiel im Artikel Abschnitt 5.1: Die erste Permutation ${\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}$ vertauscht 2 und 3, die anschließende Permutation ${\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}$ bringt die 3 wieder an die Ausgangsposition. Die Komposition ${\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}$ dagegen bringt die 3 auf den Platz der 1.

Deshalb ist richtig die Interpretation "Lege das Element $\pi (x_{i})$ auf den Platz von $x_{i}$". Das passt zur Permutationsmatrix und zur Komposition. Diese Interpretation setzt voraus, dass die zu permutierenden Objekte mit den Indizes $i=(1...n)$ beschriftet sind, sonst könnte man sie nicht als "das" Objekt $x_{i}$ ansprechen.

Wenn die zu permutierenden Objekte nicht mit den Indizes $i=(1...n)$ beschriftet sind sondern die Plätze, wo sie sich gerade befinden, dann ist richtig die Interpretation "Lege das Objekt vom Platz $i$ auf den Platz $\pi (i)$". Das passt ebenfalls zur Permutationsmatrix und zur Komposition. --2003:CA:6F23:3C31:D008:7987:C14E:49C2 15:51, 14. Sep. 2024 (CEST)

Wollte gerade dasselbe anmahnen. Hab's geändert - hoffentlich nichts übersehen, und hoffentlich hat sich der Fehler nicht schon weiter ausgebreitet. Z.B. wird auch in https://de.wiki.x.io/wiki/Fixpunktfreie_Permutation von den $\pi (x_{i})$ als den Plätzen der Elemente $x_{i}$ gesprochen, muss ich wohl auch noch ran.

--95.90.244.176 07:56, 22. Sep. 2024 (CEST)

Den erneuten Änderungsversuch möchte ich(=14.Sep.) unterstützen. In der Artikelversion vom 22.Sep. ist noch nicht die Überlegung vom ersten Disskusionsbeitrag 4.Nov.2023 berücksichtigt: "Egal wie rum, aber es sollten nicht Elemente auf Plätze, oder Plätze auf Elemente abgebildet werden, sondern immer nur auf die betrachtete Menge selbst". Auch die Formulierung "Anschaulich" ist nicht ausreichend, weil da nicht mit gesagt wird, was man da anschauen soll. Die Pfeile bei der Abbildung? Die haben eine andere Bedeutung. Sie zeigen anschaulich nicht an, welches Element wohin gebracht werden soll. Das hätte bei einer Menge keine Wirkung. Die Menge $\{2,4,3,1\}$ ist nicht unterscheibar von der Ausgangsmenge $\{1,2,3,4\}$, da kann man tauschen wie man will. Die Pfeile bei der Abbildung haben die Bedeutung, das Element $i$ wird auf das Element $\pi (i)$ abgebildet. Anschaulich bedeutet das eher sowas wie ein Foto von $i$ wird auf das Element $\pi (i)$ projiziert oder zum Beispiel der Schattenumriß bei geeigneter Beleuchtung. Dem Pfeil kann man erst eine Bedeutung als Bewegung zuschreiben, wenn jedem zu permutierenden Objekt ein Platz zugeordnet ist. Dann kommt es darauf an, ob die zu permutierenden Objekte mit $i=1,...,n$ beschriftet sind oder die Plätze. Im ersten Fall ist "Lege das Objekt $\pi (i)$ auf den Platz von Objekt $i$" die zur Permutationsmatrix und Komposition passende Bewegung. Im zweiten Fall ist "Lege das Objekt von Platz $i$ auf den Platz $\pi (i)$" die zur Permutationsmatrix und Komposition passende Bewegung. In beiden Fällen werden mit $i$ und $\pi (i)$ entweder nur die zu permutierenden Objekte bezeichnet oder nur Plätze. --2003:CA:6F23:3C31:6985:BB9B:9DE1:92B 02:24, 28. Sep. 2024 (CEST)