www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikAlgorithmus-Nummer Permutation
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Diskrete Mathematik" - Algorithmus-Nummer Permutation
Algorithmus-Nummer Permutation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Algorithmus-Nummer Permutation: Tipp - Idee
Status: (Frage) beantwortet Status 
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.


        
Bezug
Algorithmus-Nummer Permutation: Antwort
Status: (Antwort) fertig Status 
Datum: 15:18 Di 28.02.2012
Autor: Al-Chwarizmi


> 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.





Bezug
                
Bezug
Algorithmus-Nummer Permutation: Frage (überfällig)
Status: (Frage) überfällig Status 
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!



Bezug
                        
Bezug
Algorithmus-Nummer Permutation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Algorithmus-Nummer Permutation: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Di 06.03.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                
Bezug
Algorithmus-Nummer Permutation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:07 Di 28.02.2012
Autor: felixf

Moin,

bei der Wikipedia findet sich auch etwas []zum Thema.

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]