列表理解：列出列表

嗨即時嘗試在haskell中使用數字a函數使用列表的一個部分，即數字4它會創建[[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]。我正在考慮使用列表理解來創建列表x，然後使用[1 ... n]中的數字（n是我想要的分區編號）創建更多列表，其中創建列表的總和相等到n。列表理解：列出列表

的代碼，我創建至今是 -

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

但obiviously它不工作，有什麼建議？

謝謝。

來源

2010-11-16 dave

軋製回殺害後 – 2010-11-23 00:00:33

又一次的編輯。 @dave，你爲什麼試圖刪除你的問題？：/ – 2010-11-23 00:03:11

我建議嘗試遞歸：要獲得n的分區，遍歷數字i = 1到n，並遞歸生成（ni）的分區，基本情況是1的唯一分區是1本身，而0的分區是空列表。

來源

2010-11-16 17:50:01 Lagerbaer

使'分區0'爲'[[]]'而不是'[]'可能有助於簡化遞歸。 – 2010-11-17 03:09:01

@Joey的確如此。我在描述自己會做什麼的時候有點sl sl。 – Lagerbaer 2010-11-17 15:31:36

我對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

編輯

當x等於0至返回我已經固定在底座部分的情況下列表中只有一個項目，該項目是一個空列表。現在，它工作得很好:)

來源

2010-11-16 17:56:33 Fede

也許我失去了一些東西，但我得到一個錯誤：無法匹配預期類型t1-> t對推斷類型[[Int]]。在表達式中：第4部分1.在'it'的定義中：it = part 4 1 – 2010-11-19 16:47:58

@Matt我不是專家，但我認爲你可能在另一個環境中使用'it'，並且'它'與[[Int]]不匹配。我使用WinHugs調用'parts 4 1'，輸出與@dave的示例完全相同 – Fede 2010-11-19 17:37:24

您不應該定義'it'。 '它'總是GHCi中最後一次計算的結果。 – nomen 2012-12-11 00:38:13

這個怎麼樣...

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

我認爲這是正確的，如果效率不高。

來源

2010-11-17 00:43:03

我發現定義輔助函數partitionsCap是有幫助的，它不會讓任何項目大於給定值。遞歸使用，它可用於僅生成所需的monotonically減少的結果（即沒有0，當你已經有[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和地圖那麼密切了我的注意。一點背景：列表解析和列表monad是very closely related，而concatMap與>>=相同，其參數在列表monad中翻轉。所以我想知道：可以那些concat和地圖莫名其妙變成>>=，並且那>>=可以以某種方式甜言蜜語進入列表理解？

在這種情況下，答案是肯定的:-)

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

來源

2010-11-17 03:45:50

列表理解：列出列表

回答

相關問題