Permutations Algorithmus



  • Hi

    ich versuche mir ein Permutations Algorithmus zusammen zu programmieren, komm aber leider auf keine brauchbare Lösung (habs rekursiv hinbekommen, klappt aber nur bei kleineren Mengen)

    mein Ansatz jetzt ist das ganze so anzugehen:
    ich ordne die Permutationen nach folgendem Schema:
    (1,2,3,4... steht für die Stelle)
    x0|x1|x2|x3
    1 2 3 4 (= 1.)
    1 2 4 3 (= 2.)
    1 3 2 4 (usw..)
    1 3 4 2
    1 4 2 3
    1 4 3 2
    2 1 2 3
    usw...

    dann kann ich mir so ausrechnen an welcher Stelle eine Permutation ist:

    f(x0,...,xn-1)=[ ∑i=0n-1 pos(xi)*(n-i-1)! ] +1

    wobei pos() angibt an welcher Position die Zahl in einer der Größe nach geordneten Menge stehen würde (gezählt wird ab 0)

    z.b bei der 5. Permutation (1 4 3 2)
    kommt bei pos(x1) dann 2 raus
    da 4>3>2 (nur die x dazu, die weiter rechts stehen)

    so und falls f jetzt umkehrbar wäre und ich die Umkehrfunktion wüsste könnt ich mir ganz leicht die i-te Permutation ausgeben lassen....
    aber genau da komm ich net weiter
    ich hoff hier kann mir jemand weiterhelfen 🙂



  • Permutationen bilden Gruppen !

    Aus deinem Post wird leider nicht klar, ob du dein Zählalgorithmus über alle möglichen Permutationen laufen soll, oder über die Permutationen die länge X haben.

    In deinem Beispiel mit "4" vermisse ich beispielsweise folgende :

    ( 1 2 ) ( 3 4 )
    oder wie stehts mit
    ( 1 2 3 ) ( 4 )

    Deswegen denke ich, ein bißchen Gruppentheorie kann dir nicht schaden ...

    Im grunde genommen rechnet man alle Permutation zurück auf 2er-Zykel.

    pos ( 1 2 ) = 0
    pos ( 2 1 ) = 1

    Da du alle längeren Zykel aus 2er Zykel zusammensetzen kannst, mußt du deine "große Permutation" nur Zerlegen und die 0/1 zusammen zählen.

    Das bringt mich wieder auf den (üblichen) Punkt, Formeln zu benutzen, ohne zu wissen, was sie bedeuten ...

    Zum Schluß noch zwei Rechenaufgaben :

    ( 1 3 4 ) ( 2 4 5 3 ) = ?
    ( 1 3 7 ) ( 6 4 3 2 7 5 1 ) = ?

    Gruß




Log in to reply