Algorithmus-Nummer Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:09 Di 28.02.2012 | | Autor: | Stevuu |
Hallo Community,
ich habe eine Frage zu einem Problem, dass mich jetzt schon ein paar Tage beschäftigt (wäre super froh, wenn ihr mich helfen könntet):
Also es geht um Permutationen
also nehmen wir z.B. die Permutationen von {a,b,c}
ich habe n! also 3! mögliche Permutationen.
Die Permutationen wären: abc ,acb , bac , bca , cab ,cba
Soweit so gut. Jetzt zur eigentlichen Essenz der Frage.
Ich suche einen Algorithmus, mit dem ich die Nummer der Permutation bestimmen kann.
Also ich suche quasi einen Algorithmus, der mir aufgrund der Angabe von bca ermittelt, dass ist die 4te mögliche Permutation von {a,b,c}
Oder eben cba -> 6te mögliche Permutation.
Mir ist klar, dass das natürlich auch von der Sortierung abhängt.
abc -> 1
acb -> 2
bac -> 3
bca -> 4
cab -> 5
cba -> 6
Kann ich natürlich nur sagen, wenn ich dieses Sortierungsschema voraussetze (aber das wäre ja ok)
Gibt es da einen Berechnungsweg bzw. Algorithmus?
(also den Algortihmus, alle Permutationen von {a,b,c} bis zu der gesuchten zu ermitteln und durchzunummerieren gibt es ja schon mal sicher. (habe ich ja quasi oben durchgeführt. Aber ich suche einen einfacheren Weg, weil ist ja irgendwie klar, wenn man 100! hat ist dieser Weg dann zu aufwändig.)
Vielen Dank, für eure Bemühungen!!
Und falls ihr nichts wisst ist es auch nicht so schlimm...ich überlege nu au schon 2 Tage ohne nennenswertes Ergbenis ;)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo Community,
> ich habe eine Frage zu einem Problem, dass mich jetzt
> schon ein paar Tage beschäftigt (wäre super froh, wenn
> ihr mich helfen könntet):
ich werde dich nicht helfen, aber dir !
> Also es geht um Permutationen
> also nehmen wir z.B. die Permutationen von {a,b,c}
> ich habe n! also 3! mögliche Permutationen.
>
> Die Permutationen wären: abc ,acb , bac , bca , cab ,cba
>
> Soweit so gut. Jetzt zur eigentlichen Essenz der Frage.
>
> Ich suche einen Algorithmus, mit dem ich die Nummer der
> Permutation bestimmen kann.
>
> Also ich suche quasi einen Algorithmus, der mir aufgrund
> der Angabe von bca ermittelt, dass ist die 4te mögliche
> Permutation von {a,b,c}
> Oder eben cba -> 6te mögliche Permutation.
>
> Mir ist klar, dass das natürlich auch von der Sortierung
> abhängt.
>
> abc -> 1
> acb -> 2
> bac -> 3
> bca -> 4
> cab -> 5
> cba -> 6
>
> Kann ich natürlich nur sagen, wenn ich dieses
> Sortierungsschema voraussetze (aber das wäre ja ok)
>
> Gibt es da einen Berechnungsweg bzw. Algorithmus?
>
> (also den Algorithmus, alle Permutationen von {a,b,c} bis
> zu der gesuchten zu ermitteln und durchzunummerieren gibt
> es ja schon mal sicher. (habe ich ja quasi oben
> durchgeführt. Aber ich suche einen einfacheren Weg, weil
> ist ja irgendwie klar, wenn man 100! hat ist dieser Weg
> dann zu aufwändig.)
Hallo Stevuu,
die Permutationen sollen also lexikographisch (wie im
Lexikon oder im Telefonbuch) angeordnet werden.
Nehmen wir doch ein etwas längeres Beispiel,
damit das Prinzip wirklich klar wird:
die wievielte Permutation der Buchstaben <a,b,c,d,e>
ist <d,c,a,e,b> ?
Die gesamte Liste aller 5!=120 Permutationen zerfällt
in 5 Gruppen zu je 4!=24 Permutationen, welche mit
a, b, c, d, e beginnen. Da unsere Permutation mit einem
"d" beginnt, stehen in der Liste alle mit a, b oder c
beginnenden, also $\ 3*4!$ Stück, davor.
Jetzt wird der zweite Buchstabe betrachtet: vor dem "c"
in unserer Permutation stehen die (noch nicht benützten)
Buchstaben a und b, insgesamt also $\ 2*3!$ Permutationen.
Dann so weiter mit dem dritten und vierten Buchstaben.
Der letzte, noch verbleibende Buchstabe ist dann zwangs-
läufig das übrig gebliebene "b".
Vor der betrachteten Permutation <d,c,a,e,b> stehen in der
Liste also insgesamt $\ 3*4!+2*3!+0*2!+1*1!\ =\ 85$ Permutationen,
die betrachtete ist also die 86ste .
Wenn man nun daraus einen "automatischen" Algorithmus
machen will, nimmt man anstelle der Buchstaben a,b,c, ...
besser die Zahlen 1,2,3, ...
Für die Nummer N(p) einer Permutation [mm] p=
[/mm]
ergibt sich dann ein Ausdruck der Form
$\ N(p)\ =\ [mm] 1+\sum_{k=1}^{n-1} c_k*(n-k)! [/mm] $
Dabei ist [mm] c_k [/mm] gleich der Anzahl der Elemente in der
Menge [mm] $\{1,2,3,\,...\,,n\}\smallsetminus\{\,p_1,\,...\,,\,p_{k}\,\}\,$ [/mm] , welche kleiner als [mm] p_k [/mm] sind.
Ich hoffe, dass ich dies richtig notiert habe ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:02 Di 28.02.2012 | | Autor: | Stevuu |
Hallo, Al-Chw,
super vielen Dank, das ist genau die Antwort die ich gesucht habe. Auch super verständlich erklärt. Echt genial :)
Freu mich gerade total, dass ich so eine gute Antwort bekommen hab :D
Hätte noch zwei Erweiterungen bzw. weitergehende Fragen, die ich anfangs nicht mit gepostet hatte, um es nicht unnötig kompliziert zu machen.
1. Ich brächte den Algorithmus für "Permutationen von klassenweise äquivalenten Objekten"
Heißt quasi nicht <d,c,a,e,b> sondern meinetwegen
<d,d,a,e,b>
(wobei sich die d's nicht unterschieden)
Also Al-Chw. Antwort etwas modifiziert.
2. Wenn ich dann den Agorithmus aus 1. habe.
Komme ich dann mit dem Ergebnis wieder zum Ursprung zurück...? Also gibt es quasi eine Umkehrung?
Also diesmal nicht <d,d,a,e,b> -> 34 (oder so)
sondern 86 + {a,b,d,d,e} -> <d,d,a,e,b>
Ich würde also die Menge + die Nummer der Permutation mitgeben und daraus hätte ich dann gerne die Reihenfolge quasi.
Fänd es echt toll, wenn mir hier auch noch jmd. helfen könnte.
Muss zwar nun erstmal bisschen was zu essen einkaufen gehen, aber ich werde natürlich auch versuchen auf eine Lösung zu kommen. Durch Al-Chew. hab ich ja jetzt schon mal einen Ansatz *freu*.
(soll jetzt nicht heißen, dass Antworten obsolet werden könnten, falls ich eine plausible Lösung erarbeite brauche ich sowieso nochmal einen Gegencheck, bin leider mathematisch ein paar Level unter manchen hier, die sich wirklich super auskennen)
*edit* 23:47 Uhr
bin schon ganz wirr vom nachdenken....aber ich komm irgendwie nicht drauf....hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:31 Mi 29.02.2012 | | Autor: | Stevuu |
Hey, ich habe jetzt mal drüber geschlafen und noch bissl nachgedacht und ich glaube ich habe eine Lösung zu Punkt 1 meiner erweiterten Fragen.
Also der Anpassung des Algorithmus den mir Al-Chw. gepostet hat auf Permutationen von klassenweise äquivalenten Objekten.
Der Algorithmus zum lexikographischen Nummerierung der Permutationen war ja:
$ \ N(p)\ =\ [mm] 1+\sum_{k=1}^{n-1} c_k\cdot{}(n-k)! [/mm] $
Al-Chw. hatte seine Formel / Algorithmus ja so aufgestellt, in dem er von folgendem ausging
> Die gesamte Liste aller 5!=120 Permutationen zerfällt
> in 5 Gruppen zu je 4!=24 Permutationen, welche mit
> a, b, c, d, e beginnen. [....usw.]
Das dürfte ja jetzt mit den klassenweise äquivalenten Objekten ähnlich sein.
Nur dass die nicht in n! zerfallen, sondern in
n! / l1!*l2!...lk! laut wiki
(http://de.wikipedia.org/wiki/Abz%C3%A4hlende_Kombinatorik#Permutationen_von_klassenweise_.C3.A4quivalenten_Objekten) wobei l1, l2, l3 usw. die Gruppen von gleichen Elementen sind
Auf jeden Fall bin ich zum Schluss gekommen die Formel/ Algorithmus müsste nun lauten:
$ \ N(p)\ =\ [mm] 1+\sum_{k=1}^{n-1} c_k\cdot{}((n-k)! [/mm] / [mm] l_1!*l_2!*...*l_k! [/mm] ) $
wobei bei l1 - lk eben immer die noch vorhandenen Gruppengrößen von äquivalenten Objekten stehen.
Ich denke mal meine mathematische Ausdrucksweise dürfte nicht ganz korrekt sein :)
Verbesserungen sind gerne gesehen, lerne da gerne dazu.
Was ich noch super gerne wissen würde ist, stimmt meine Annahme vom Prinzip her? (ich hab das zwar jetzt schon an einigen Bsp. probiert...aber vlt. wars ja Zufall, dass es immer hingehauen hat)
Vieelen Dank euch schonmal!!!
Ah ja, mein 2. Teil meiner erweiterten Nachfrage ist leider auch noch offen. Da komme ich irgendwie noch nicht auf eine Lösung. Vlt hat da ja noch jmd Tipps oder Ansätze.
Hier nochma die Frage:
2. Wenn ich dann den Agorithmus aus 1. habe.
Komme ich dann mit dem Ergebnis wieder zum Ursprung zurück...? Also gibt es quasi eine Umkehrung?
Also diesmal nicht <d,d,a,e,b> -> 34 (oder so)
sondern 86 + {a,b,d,d,e} -> <d,d,a,e,b>
Ich würde also die Menge + die Nummer der Permutation mitgeben und daraus hätte ich dann gerne die Reihenfolge quasi.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Di 06.03.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:07 Di 28.02.2012 | | Autor: | felixf |
Moin,
bei der Wikipedia findet sich auch etwas ![[]](/images/popup.gif) zum Thema.
LG Felix
|
|
|
|
