Понимание списка: составление списков списков

Question

Привет, я пытаюсь создать функцию в haskell, которая принимает число a, делит его на части, используя списки, то есть для числа 4 это создаст [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]. Я думал об использовании списочного понимания для этого, где он будет создавать список x, а затем создавать дополнительные списки, используя числа из [1 ... n] (n - это номер раздела, который я хотел бы), где сумма созданного списка будет равна по номеру

Код, который я создал до сих пор -

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

но, очевидно, это не работает, какие-либо предложения?

спасибо.

Answer 1

Я предлагаю попробовать рекурсию: чтобы получить разделы n, выполните итерации по числам от i = 1 до n и рекурсивно сгенерируйте разделы (ni), при этом базовый случай состоит в том, что единственным разделом 1 является сам 1, ираздел 0 - пустой список.

Answer 2

Как насчет этого ...

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)]

Попытка:

*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]]

Я думаю, что это правильно, если не эффективно.

Answer 3

Мне показалось полезным определить вспомогательную функцию partitionsCap, которая не позволяет ни одному из элементов быть больше заданного значения. Используемый рекурсивно, он может использоваться только для монотонного получения желаемых результатов с уменьшением (т. Е. Нет [1,3,1], когда у вас уже есть [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

---

В основе алгоритма лежит идея, что при разбиении N вы берете i с n до 1 и добавляете i к разделам n-i. Упрощенная:

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

но неправильно:

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

Мы хотим, чтобы [1,2] ушел. Следовательно, нам нужно ограничить разделы, к которым мы добавляем, чтобы они не превышали i:

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

Теперь, чтобы очистить это: это concat и map так близко друг к другу привлекли мое внимание. Немного предыстории: списочные выражения и монада списка очень тесно связаны , а concatMap - это то же самое, что >>= с перевернутыми аргументами в монаде списка. Так что я подумал: могут ли эти concat и map каким-то образом превратиться в >>=, и может ли это >>= каким-то сладким образом проникнуть в понимание списка?

В этом случае ответ - да: -)

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

Answer 4

Я немного устал от Haskell, но, возможно, следующий код поможет вам найти решение.

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

И тогда вам придется вызывать детали с x = n и p = 1.

EDIT

Я исправил базовый случай, когда х равен 0, чтобы вернуть список с одним элементом, поскольку этот элемент - пустой список. Теперь работает нормально :)