2010-11-17 38 views
7

Wie kann ich eine Liste [1,2,4,1,5,7,3,4,2,3] in eine Liste von Unterlisten aufteilen, die bei den Werten geteilt werden, die die Sequenz. Zum Beispiel sollte eine Liste [1,2,4,1,5,7,3,4,2,3] eine Liste von Unterlisten wie [[1,2,4], [1,5,7], [ 3,4], [2,3]].Aufteilen der Liste in sortierte Unterlisten

Irgendwelche Ideen zu diesem oder Vorschläge, wie man dieses Problem löst?

Danke.

+0

Vielen Dank Jungs, Sie waren wirklich hilfreich, haben viele gute Informationen :) –

+0

Bitte markieren Sie Hausaufgaben Fragen als Hausaufgabe. – luqui

Antwort

4

Hier ist ein Tipp: wenn Sie bei aufeinander folgenden Elementen suchen müssen, während eine Liste der Verarbeitung, es ist eine gute Idee von zippen die Liste gegen den Schwanz zu starten:

Prelude> let f xs = zip xs $ tail xs 
Prelude> f [1,2,4,1,5,7,3,4,2,3] 
[(1,2),(2,4),(4,1),(1,5),(5,7),(7,3),(3,4),(4,2),(2,3)] 

Jetzt können Sie so etwas wie splitWhen $ uncurry (>) verwenden (wo splitWhen ist von Data.List.Split), um die Liste entsprechend zu unterteilen.

2

Sie können es mit 2 Funktionen tun, eine, die den Kopf teilt, während das erste Element niedriger als die zweite ist, und ein anderes, das die Ausgabe der Funktion übernimmt, die den Kopf teilt, und das Ergebnis eines rekursiven Aufrufs zu selbst mit dem Schwanz der Liste.

splitList :: [Int] -> [[Int]] 
splitList [] = [] 
splitList (x:xs) = ys : splitList zs 
    where (ys,zs) = splitHead (x:xs) 


splitHead :: [Int] -> ([Int], [Int]) 
splitHead [x] = ([x], []) 
splitHead (x:y:xs) 
    | x > y = ([x], (y:xs)) 
    | x <= y = (x:ys, zs) 
    where (ys,zs) = splitHead (y:xs) 
+0

Grund für den Downvote bitte. Ich habe meine Lösung in WinHugs getestet und funktioniert wie ein Zauber. Ist es ineffizient? – Fede

9

wie Travis oben, mein erster Gedanke ist, die Liste mit dem eigenen Schwanz zip: jedoch es nicht aussehen, wie es ganz in dieser Situation funktioniert. Es gibt nicht nur eine Split-Funktion, die genau das tut, was Sie wollen, sondern es gibt auch das Problem, dass Sie ein Element entweder am Anfang oder am Ende verlieren. Anstelle einer richtig abstrahiert Lösung, werfen Sie einen Blick auf diese:

splitAscending :: Ord a => [a] -> [[a]] 
splitAscending = foldr f [] where 
    f x [] = [[x]] 
    f x (y:ys) = if x < head y 
    -- It's okay to call head here because the list y is 
    -- coming from the summary value of the fold, which is [[a]]. 
    -- While the sum value may be empty itself (above case), it will 
    -- never CONTAIN an empty list. In general be VERY CAREFUL when 
    -- calling head. 
     then (x:y):ys -- prepend x to the first list in the summary value 
     else [x]:y:ys -- prepend the new list [x] to the summary value 

A quick and dirty Lösung, ich hoffe, dass es Ihren Bedürfnissen entspricht

- Auch dies ist mein erster Beitrag auf Stack-Überlauf:)

+0

Ich mag diese Lösung und denke, es ist wahrscheinlich ein bisschen einfacher als meins, aber es ist sicherlich auch möglich, dies mit dem Tail-Zipping-Ansatz zu implementieren (Sie müssen nur etwas tun wie 'map (\ ys -> fst (head ys): map snd ys) 'nach' splitWhen'). –

2

Nun, das ist nicht so sauber wie ich es gerne hätte, aber hier ist es. Mit Paket aufgeteilt: http://hackage.haskell.org/package/split

:m+ Data.List.Split 
Prelude Data.List.Split> let f ys = let ys' = zip ys (tail ys) in map (map fst) ((split . whenElt) (uncurry (>)) $ ys') 

Die Streben sehr wahrscheinlich hier gereinigt werden können.

1

Wie wäre es

asc [] = [[]] 
asc (x:xs) = map reverse $ reverse $ foldl ins [[x]] xs 
    where ins ((y:ys):yss) z | z > y = (z:y:ys) : yss 
          | otherwise = [z] : (y:ys) : yss 

oder

asc = map reverse.reverse.foldl ins [[]] 
     where ins [[]] z = [[z]] 
      ins ((y:ys):yss) z | z > y = (z:y:ys) : yss 
           | otherwise = [z] : (y:ys) : yss  

?

Verwandte Themen