Haskell: Permutationen

[hugs]

Hi,

leider bringt mich Haskell noch zur Verzweiflung.
Würde gerne anhand eines gegebenen Strings alle Permutationen finden, die man mit den einzelnen Chars des Eingabestrings bilden kann:

Dazu soll z.B. permutations "ab" aufgerufen werden und ungefähr sowas zurückgegeben werden: ["a","ab","ba","b"]

permutations übergibt die Aufgabe an px, welche dann "Buchstabe für Buchstabe" einen String zusammensetzt indem es an jeder beliebigen Stelle einen Char einfügt und somit alle Kombinationen abdeckt. Dann wendet es sich selbst wieder auf die neuen Zeichenketten an usw.
Soviel zur Theorie... Was passiert, ist, dass die Rückgabe ["a",""] ist :(

permutations :: String -> [String]
permutations s = px [""] s

px :: [String] -> String -> [String]
px ssold []=[[]]
px [""] snew=px [[head snew]] (tail snew)
px ssold snew = ssold ++ px (foldr1 (++) [pc (head snew) sold|sold<-ssold]) (tail snew)

pc :: Char -> String -> [String]
pc c s = [insByPos c s pos|pos<-[0..((length s)-1)]]

insByPos :: Char -> String -> Int -> String
insByPos c s pos = take pos s ++ [c] ++ drop pos s

Hoffe, ihr habt einen guten Rat.
Danke schonmal

[Christian Seiler]

Hallo,

Dazu soll z.B. permutations "ab" aufgerufen werden und ungefähr sowas zurückgegeben werden: ["a","ab","ba","b"]

Ich habe kurz versucht, durch Deinen Code durchzusteigen und muss sagen, dass mir irgendwie alles im Kopf herumschwirrt. ;-)

Ich hab eine Idee aus Deinem Code genommen (das Einfügen an alle Zwischenstellen) und den Rest mir selbst mal überlegt:

permutations :: String -> [String]  
permutations s = filter (/= "") (phelp s)  
     where  
         phelp "" = [""]  
         phelp (x:xs) = phelp xs ++ concat [ins x y | y <- phelp xs]  
         ins c s = [(take pos s ++ [c] ++ drop pos s) | pos <- [0..(length s)]]

Das macht genau das, was Du willst. Ich hoffe, der Code ist selbsterklärend, wenn Du noch eine Erklärung willst, reiche ich die gerne nach.

Viele Grüße,
Christian