Permutationen,k-te Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:57 Sa 10.11.2012 | | Autor: | Lu- |
| Aufgabe | | Finde eine möglichst einfache Methode, um die k–te Permutation der $ [mm] \mathcal{S}_n [/mm] $ in lexikographischer Ordnung zu finden. |
Ich verstehe die Frage nicht.
Alle Permutationen von [3] in lexikographischer Ordnung:
Es gibt 3!=6 Permutationen, diese lauten
123
132
213
231
312
321
Nun ist gefragt nach der k-ten Permutation von [mm] S_3.
[/mm]
Ich wähle k=2
Dann kommt im bsp ja jede Ziffer 2mal als k-te Zahl vor.
Was verlangt man nun zu wissen?
Liebe Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:39 Sa 10.11.2012 | | Autor: | Teufel |
Hi!
Nein, die 2. Permutation ist das 2. Ding in deiner Liste, also 132.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:02 So 11.11.2012 | | Autor: | Lu- |
Bei einer Aufgabe war ich lange nicht mehr so ratlos wie bei dieser..
Idee:
Die Anzahl der Permutationen mit i(i fix) beginnend sind (n-1)!.
Die Anzahl der Permutationen mit i, s (i,s fix in dieser Reihenfolge) beginnend sind (n-2)!
...
Wird nun ein beliebiges k [mm] \in \{1,2..,n!\} [/mm] gewählt, schaue ich unter welchen Permutation mit gleicher erster Ziffer die k-te Permutation ist.
Dann schaue ich unter den (n-1)! Permutationen unter welchen Permutationen mit gleicher zweiten Ziffer es sich befindet. Unter den (n-2)! Permutationen schaue ich unter welchen Permutationen mit gleicher dritter Ziffer es sich befindet...usw.
Zuletzt unter den (n-(n-2))!=2 Permtationen uschaue ich unter welcher Permutation mit gleidher vorletzten Ziffer es sich befindet.
Und habe nun die richtige Permutation.
Frage:
Dann würde das ganze doch die "triviale" Abzählmethode hinauslaufen, die wir nicht als Lösung verwenden sollen?
Muss ich hier eine Formel herleiten oder was soll das am ende werden?
I need help ;=)
LG
|
|
|
| |
|
Hallo Lu-,
> Bei einer Aufgabe war ich lange nicht mehr so ratlos wie
> bei dieser..
Sieht gar nicht danach aus. 
> Idee:
> Die Anzahl der Permutationen mit i(i fix) beginnend sind
> (n-1)!.
> Die Anzahl der Permutationen mit i, s (i,s fix in dieser
> Reihenfolge) beginnend sind (n-2)!
> ...
>
> Wird nun ein beliebiges k [mm]\in \{1,2..,n!\}[/mm] gewählt, schaue
> ich unter welchen Permutation mit gleicher erster Ziffer
> die k-te Permutation ist.
> Dann schaue ich unter den (n-1)! Permutationen unter
> welchen Permutationen mit gleicher zweiten Ziffer es sich
> befindet. Unter den (n-2)! Permutationen schaue ich unter
> welchen Permutationen mit gleicher dritter Ziffer es sich
> befindet...usw.
> Zuletzt unter den (n-(n-2))!=2 Permtationen uschaue ich
> unter welcher Permutation mit gleidher vorletzten Ziffer es
> sich befindet.
> Und habe nun die richtige Permutation.
>
> Frage:
> Dann würde das ganze doch die "triviale" Abzählmethode
> hinauslaufen, die wir nicht als Lösung verwenden sollen?
> Muss ich hier eine Formel herleiten oder was soll das am
> ende werden?
Nein, das ist durchaus kürzer als die Abzählmethode. Du ermittelst in (n-1) Schritten die richtige Permutation.
> I need help ;=)
Nö. Das ist die richtige Lösung. Oder sagen wir besser: eine richtige. Vielleicht gibt es ja noch andere, aber ich kenne in dieser Kürze noch keine.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:37 Mi 14.11.2012 | | Autor: | Lu- |
Ich wollte auch nochmal danke sagen, für die Korrketur.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:47 Mi 14.11.2012 | | Autor: | reverend |
Hallo Lu-,
> Ich wollte auch nochmal danke sagen, für die Korrektur.
Gern geschehen! Dafür ist das Forum ja da, und darum engagieren sich auch viele Helferinnen und Helfer.
Trotzdem ist so ein Dank ab und zu auch was Schönes. 
lg
reverend
|
|
|
|
