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

Haskell 数字的分区

Haskell Partitions of a number

haskell