k-te Permutation der S_n < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:36 Mi 09.11.2011 | | Autor: | clemenum |
| Aufgabe | | Finde eine möglichst einfache Methode, um die $k$–te Permutation der [mm] $\mathcal{S}_n$ [/mm] in lexikographischer Ordnung zu finden. |
Das einzige, was mir dazu (und das jedoch ziemlich schnell) einfällt ist die allen wohl vertraute "triviale" Methode:
Man erzeuge alle n! Permutationen der [mm] $S_n,$ [/mm] ordne sie lexikographisch und wähle das $k$–te Element — gilt hier natürlich nicht als "einfach"...
Anders als die Auflistung der Anordnungen komme ich leider nicht zur k-ten Permutation. Es ist ja offenbar eine Formel gesucht die - etwa nach gefragter Implementierung - möglichst speichersparend ist, also nicht die Vorgänger braucht um die k-te zu berechnen... Ich sehe aber leider nicht, wie es anders als rekurisiv gelingen soll...
Eine Formel scheint hier nicht elementar angebbar zu sein! Stimmt ihr mir zu?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:04 Mi 09.11.2011 | | Autor: | felixf |
Moin!
> Finde eine möglichst einfache Methode, um die [mm]k[/mm]–te
> Permutation der [mm]\mathcal{S}_n[/mm] in lexikographischer Ordnung
> zu finden.
> Das einzige, was mir dazu (und das jedoch ziemlich
> schnell) einfällt ist die allen wohl vertraute "triviale"
> Methode:
> Man erzeuge alle n! Permutationen der [mm]S_n,[/mm] ordne sie
> lexikographisch und wähle das [mm]k[/mm]–te Element — gilt hier
> natürlich nicht als "einfach"...
Nein, das ist sicher nicht gemeint 
> Anders als die Auflistung der Anordnungen komme ich leider
> nicht zur k-ten Permutation. Es ist ja offenbar eine Formel
> gesucht die - etwa nach gefragter Implementierung -
> möglichst speichersparend ist, also nicht die Vorgänger
> braucht um die k-te zu berechnen... Ich sehe aber leider
> nicht, wie es anders als rekurisiv gelingen soll...
Liste doch mal alle Permutationen in [mm] $S_3$ [/mm] und [mm] $S_4$ [/mm] auf, lexikographisch geordnet.
Welche Indices haben die Permutationen, die mit 1, 2, 3 (und 4 bei [mm] $S_4$) [/mm] anfangen? Faellt dir was auf?
LG Felix
|
|
|
|
