haskell - 如何生成固定长度的数字来总结 Haskell 中的给定数字

Question

我是 Haskell 世界的新手，想知道，给定任何正整数和 1-9 之间的位数，如何使用以下方法找到总和为正整数的数字的组合提供了 Haskell 中的位数。例如，4 使用两位数字可以表示为 [[2,2],[3,1]] 列表，使用三位数字可以表示为 [[1,1,2]] 列表，使用两位数字的 5 可以表示为 [[2,3],[4,1]] 的列表，使用三位数字可以表示为 [[1,1,3], [2,2,1]]

Answer 1

假设您想避免暴力破解方法，这可以视为典型的 dynamic-programming问题:

import Data.Array

partitions :: Int -> Int -> [[Int]]
partitions m n = table ! (m, n, 9)
  where
    table   = listArray ((1, 1, 1), (m, n, 9)) l
    l       = [f i j k | i <- [1 .. m], j <- [1 .. n], k <- [1 .. 9]]

    f i 1 k = if i > k `min` 9 then [] else [[i]]
    f i j k = [d : ds | d <- [1 .. k `min` pred i], ds <- table ! (i - d, j - 1, d)]

这个想法是构造一个三维惰性数组table，其中索引为(i, j, k)的单元格包含所有分区ds 将正整数 i 转换为从 [1 .. k] 中提取的 j 位数字列表，使得 sum ds = =我。

例如:

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

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

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

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