递归整数分区算法

Question

我正在尝试计算我可以对整数进行多少种分区。到目前为止，我想出了以下功能：

def partition(num: Int): Int = {
    if(num == 1) return 1
    if(num <= 0) return 0
    return partition(num-1) + partition(num-(num-1))
}
partition(6) //6 instead of 7  

例如：5 -> 4 + 1, 3 + 2, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1

如果 num 是 1，它返回 1，因为我认为partition(1)是结束。

也许您可以发现其中的逻辑错误？

Answer 1

我认为这有效：

def partition(n: Int): Int = {
  def inner(n: Int, max: Int): Int =
    if (n == 0) 1
    else if (n < 0) 0
    else ((1 to max) map (x => inner(n - x, x))).sum
  if (n == 0) 0
  else inner(n, n-1)
}

整数n可以划分为(n-1) + (any way of partitioning 1)、(n-2) + (any way of partitioning 2)、...、1 + (any way of partitioning (n-1))。但是，天真地计算m = 1 to n-1的partition(m)并对结果求和会将一些划分n的方法计算两次，例如 1 + (n-1)和(n-1) + 1 .

我们可以通过将分区视为i{j} < n总和为 n 的正整数序列来解决这个问题，并且只考虑有序的序列。inner方法有一个max参数，可确保它仅考虑具有i{j} >= i{j+1}的序列。所以它会考虑例如 2 + 1，但不是1 + 2。

n == 0上面的代码中是一个烦人的边缘情况，因为您实际上不想计算空序列。

Answer 2

def partition(n: Int): Int = {
    def partDecr(n: Int, decr: Int): Int = {
        if (n == 0) 1
        else if (n < 0 || decr == 0) 0
        else partDecr(n - decr, decr) + partDecr(n, decr - 1)
    }
    partDecr(n, n)
}

• 内部函数采用一个额外的参数，指定下一个可能的递减。
• 首先，它检查我们是否处于有效的终点（找到 1 个解决方案）。
• 然后它检查我们是否可以继续（正休息到分区，正递减下一步尝试）。
• 然后它递归为 2 种方式：
  • 第一个"接受"电流递减并减少 n，
  • 第二个"跳过"当前的递减，并将尝试下一个较低的递减。

请注意，这不是尾递归，可以使用相当多的堆栈空间，但它太慢了，无关紧要。

Answer 3

我认为没有"那么简单"的算法来计算你想要的东西。OP 中提出的算法由于几个原因（我不会讨论）而不起作用。

但是我引导您到维基百科关于"分区"的条目，其中还包括一个递归公式。

请注意，这个精确的公式在计算上比OP中提出的算法更复杂，也更复杂。

Answer 4

我认为它需要另一个参数（可以组成分区的整数，称之为madeOf）。这样，您可以将问题划分为 2 个严格较小的子集。partition(num, madeOf=(n, n-1, ..., 1))的计数是

• partition(num, madeOf=(n-1, ..., 1))（所有不包含 n 的分区）
• partition(num-n, madeOf(n, n-1, ..., 1))（至少有一个 n 的所有分区）

然后，您可以使其更加优化，因为madeOf只能由一个 int 构造：

def part(num: Int, madeOf: Int): Int =
  if (num == 0) 1 // we found a partition!
  else if (num < 0) 0 // no partition...
  else if (madeOf == 0) 0 // no more ways to make partition
  else part(num, madeOf - 1) +  // all the partitions that don't contain n
    part(num - madeOf, madeOf)  // all the partition that contain n
part(5, 4) // 6

Answer 5

您可以使用

以下内部函数 - 您只需要创建一个包含数字

  def partition(number: Int, intNumbers: List[Int]): Int = {    
if (number <= 0 || intNumbers.isEmpty) 
  0
else if ((number-intNumbers.head)==0) 
  1+partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)
else 
  partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)