一个数字的Haskell分区

Question

我正在尝试创建一个程序来查找数字的每个分段。

例如，分解4的方法有：

[1, 1, 1, 1]
[1, 1, 2]
[1, 3]
[2, 2]
[4]

我在Python中用完成了这项工作

n = 4
x = [0 for i in range(n+1)]
t = [0 for i in range(n+1)]
x[0] = 1
def partition(i):
for j in range(x[i-1], (n - t[i-1])//2 + 1):
x[i] = j
t[i] = t[i-1] + j
partition(i+1)
x[i] = n - t[i-1]
print(x[1:i+1])
partition(1)

但我需要用Haskell写。有办法吗？

Answer 1

这里有一个提示：

考虑到这一点，颠倒顺序是很有价值的，所以你正试图生成：

[1, 1, 1, 1]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

因此，首先选择每个可能的第一个元素，这里是1、2、3或4。假设我们选择了1，那么还有3个。我们可以递归地计算3的所有分区，然后在每个分区前面加1。

(哦，这不太对！仍然是一个很好的起点。但你会生成例如[1,2,1]，所以我认为你需要添加一个参数，说"不要生成任何大于m的数字"(

我们必须确保基本情况正确。0有多少个分区？有一个，空分区！

Answer 2

您还可以使用可变向量对其进行字面翻译。主要的区别在于，您需要在Haskell中非常明确地分离读写，因此它会变得有点混乱。

这是我在不了解你的算法的情况下想到的：

import Data.Foldable ( for_ )
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M
main :: IO ()
main = do
let n = 4
x <- M.replicate (n + 1) 0
t <- M.replicate (n + 1) 0
M.write x 0 1
let partition i = do
x' <- M.read x (i - 1)
t' <- M.read t (i - 1)
for_ [x' .. (n - t') `quot` 2] $ j -> do
M.write x i j
t' <- M.read t (i - 1)
M.write t i (t' + j)
partition (i + 1)
t' <- M.read t (i - 1)
M.write x i (n - t')
x' <- V.freeze (M.slice 1 i x)
print (V.toList x')
partition 1