Hallo,

hier sind mal Lösungsversuche der Aufgaben 2 - 4. Mit den Permutationen der Aufgabe 5 und schlimmen Zahnschmerzen kämpfe ich leider noch.


--------------------------------

module Uebungsblatt_05 where

middle :: [a] -> a
middle xs = xs !! (( div ( length xs + 1 ) 2 ) - 1 )


allEqual :: [Integer] -> Bool
allEqual [] = True
allEqual (x:[]) = True
allEqual (x:y:xs) = x == y && allEqual ( y:xs )


merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
                    | x < y = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys

mergesort :: Ord a => [a] -> [a]
mergesort xs | length xs <= 1 = xs
             | otherwise = merge ( mergesort (take (length xs `div` 2) xs) ) ( mergesort (drop (length xs `div` 2) xs) )

--------------------------------------

Zu den Permutationen habe ich leider noch nicht die richtige Lösung gefunden.

Für middle sollte man es vielleicht noch hin bekommen, für eine leere Liste als Eingabe eine Fehlermeldung auszugeben, aber das scheitert bei mir bis jetzt an der Typisierung.

Für Ideen zu den Permutationen wäre ich dankbar!

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.

Ist das ein Locher?

Bis auf die erste Zeile könnte es ein Mathematiker sein.