Foren

Ok Leute... :-)

Hier nun eine Routine zu den Permutationen in Aufgabe 6. Leider brauchte ich aber 4 Funktionsdefinitionen, um das unter zu bringen. Die Funktion entstand nach einem Vorschlag, einer Idee von Rolf, die er mir gestern in der Bibliothek sagte. Danke dafür!

Hat wer ne Idee, wie man das gut machen kann, wenn man die Permutationen nicht rekursiv aufbaut, sondern [1..n] nimmt und dann systematisch permutiert und die Ergebnisse in eine Liste speichert?

Das hab ich leider nicht hinbekommen *schäm*.


------ Code Anfang

permutations :: Integer -> [[Integer]]
permutations x | x <= 0 = [[]]
permutations 1 = [[1]]
permutations n = addPerm n (permutations (n-1))

addPerm :: a -> [[a]] -> [[a]]
addPerm _ [] = []
addPerm n (x:xs) = addPermElem2Perm n x ++ addPerm n xs

addPermElem2Perm :: a -> [a] -> [[a]]
addPermElem2Perm n xs = addPermElemAfter (length xs) n xs where
   addPermElemAfter 0 n xs = [n:xs]
   addPermElemAfter i n xs = (take i xs ++ [n] ++ drop i xs) : addPermElemAfter (i-1) n xs

------ Code Ende


Viel Spaß beim Ausprobieren.

Das Gute dabei ist, finde ich, daß addPerm auf jedem beliebigen Listentyp arbeiten kann.
permutations ist aber deklariert, wie es in der Aufgabe gefordert war.
Wenn man das nicht so einschränkt, kann man addPerm verwenden, um beliebige Stringpermutationen zu erzeugen. Mit der Reihenfolge der Permutationen bin ich noch nicht zufrieden. Ich fände es schöner, direkt eine Ausgabe zu erzeugen, wie sie von mergesort (permutations n) mit n :: Integer geliefert wird.