k-te Permutation finden < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Finde eine möglichst eine Methode, um die k-te Permutation in lexikographischer Ordnung zu finden. |
Ich bitte euch mir für dieses Beispiel einen Tipp zu geben, da ich bis jetzt auf keine "einfache" Methode gestoßen bin.
|
|
| |
|
Hallo Tsetsefliege,
nehmen wir mal die fünf zu permutierenden Elemente A,B,C,D,E.
Wie viele Permutationen fangen (in lex.Ordnung) mit A an?
Wie viele haben auf den ersten beiden Stellen AB, in dieser Reihenfolge?
...
Die 81. Permutation ist also DBCAE, wenn mich mein Kopfrechnen nicht vollends verlässt.
Grüße
reverend
|
|
|
| |
|
Also ich habe mir das jetzt folgendermaßen angesehen:
n! = Anzahl der Permutationen
Angenommen wir betrachten die Partitionen von [4]. Durch spaltenweises Aufschreiben komme ich zur 1.Zahl. 1 Spalte = Alle Perm. die mit einer 1 anfangen, 2 Spalte = .... die mit einer 2 anfangen .....
[mm] \bruch{n!}{n} [/mm] = Anzahl der Perm. die sich in einer Spalte befinden.
[mm] \bruch{n!}{n^2-n} [/mm] = Anzahl der Perm. in einer Spalte von der Form AB
.
.
.
Wie kann daraus nun die weiterfolgenden Zahlen genau bestimmen, bzw. kann man diese Schritte auch irgendwie verallgemeinern?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:22 Do 02.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:50 Di 30.11.2010 | | Autor: | statler |
Hallo!
Erstmal ein Beispiel. die 1000. Permutation für n = 7.
Vorne steht eine 2, weil ich im 2. 720er-Block bin, 1000 : 720 = 1,..
An der 2. Stelle steht eine 4, weil ich im 3. 120er-Block bin : 280 [= (1000- 720)] : 120 = 2,.. und weil die 2 schon weg ist.
Naja, und so kann man weitermachen und dann vielleicht eine Formel entwickeln.
Gruß aus HH-Harburg
Dieter
|
|
|
|
