Zrozumienie listy: tworzenie list z listami

Question

hi im próbuje utworzyć funkcję w haskell, która pobiera liczbę a tworzy jej partycję używając list, tj. Dla numeru 4, by utworzyć [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]. Zastanawiałem się nad użyciem do zrozumienia listy, w której tworzyłoby się listę x, a następnie tworzyłoby kolejne listy za pomocą liczb od [1 ... n] (gdzie n jest numerem partycji, który bym chciał), gdzie suma utworzonej listy byłaby równa do n.

Kod Stworzyłem więc daleko jest-

partions (n:xs) = [[x|x<-[1...n], sum[x]==n]]|xs<-[1..]] 

ale obiviously nie robi praca, jakieś sugestie?

dzięki.

Answer 1

Sugeruję próbę rekursji: Aby uzyskać partycje n, należy powtórzyć liczby od i = 1 do n, i rekursywnie generować partycje (ni), przy czym podstawowym przypadkiem jest to, że jedyna partycja 1 to 1, a partycja 0 jest pustą listą.

Answer 2

Jestem trochę zardzewiały z Haskellem, ale może poniższy kod pomoże ci znaleźć rozwiązanie.

parts :: Int -> Int -> [[Int]] 
parts 0 p = [[]] 
parts x p = [(y:ys) | y <-[p..x], ys <- (parts (x - y) y)] 

I wtedy trzeba by części z X = N i P = 1.

EDIT

Naprawiłem przypadku bazowego gdy x wynosi 0 do zwróci zadzwonić lista z pojedynczą pozycją, która jest pustą listą. Teraz działa dobrze :)

Answer 3

Jak o tym ...

import Data.List (nub, sort) 

parts :: Int -> [[Int]] 
parts 0 = [] 
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)] 

Próbując go:

*Main Control.Monad> forM [1..5] (print . parts) 
[[1]] 
[[2],[1,1]] 
[[3],[1,2],[1,1,1]] 
[[4],[1,3],[1,1,2],[1,1,1,1],[2,2]] 
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[2,3]] 

Myślę, że to słuszne, czy nie skuteczny.

Answer 4

Przydało mi się zdefiniowanie funkcji pomocniczej, partitionsCap, która nie pozwala, aby którykolwiek z elementów był większy od podanej wartości. Używane rekursywnie, może być stosowane tylko do wytworzenia monotonically wynikiem malejących chcesz (to znaczy nie [1,3,1] gdy masz już [1,1,3]):

partitions :: Int -> [[Int]] 
partitions n = partitionsCap n n 

partitionsCap :: Int -> Int -> [[Int]] 
partitionsCap cap n 
    | n < 0 = error "partitions: negative number" 
    | n == 0 = [[]] 
    | n > 0 = [i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
       where hi = min cap n 

---

W sercu algorytmu jest pomysł, że gdy partycjonowanie N, bierzesz i z n w dół do 1 i dodajesz i do partycji n-i. Uproszczone:

concat [map (i:) $ partitions (n-i) | i <- [n,n-1..1]] 

ale źle:

> partitions 3 
[[3],[2,1],[1,2],[1,1,1]] 

Chcemy że [1,2] odejść.Stąd musimy cap partycje jesteśmy poprzedzenie się tak, że nie pójdzie powyżej i:

concat [map (i:) $ partitionsCap i (n-i) | i <- [hi,hi-1..1]] 
where hi = min cap n 

Teraz, aby go oczyścić: że concat i mapa tak blisko siebie moją uwagę . Trochę tła: spisane ze zrozumieniem listy i monada z listy to very closely related, a concatMap jest tym samym, co >>= z odwróconymi argumentami na liście monad. Tak więc zastanawiałem się: czy te dane mogą w jakiś sposób przekształcić się w >>=, w jakiś sposób słodko-gadający sposób na zrozumienie listy?

W tym przypadku odpowiedź brzmi tak :-)

[i : p | i <- [hi,hi-1..1], p <- partitionsCap i (n-i)] 
where hi = min cap n