1

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

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)是结束。

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

4

5 回答 5

4

我认为这有效：

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))。然而，天真地计算partition(m)和m = 1 to n-1求和结果将计算一些划分n两次的方法，例如1 + (n-1)和(n-1) + 1。

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

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

于 2012-09-28T15:44:39.870 回答
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 ，
    • 第二个“跳过”当前递减，并尝试使用下一个较低的递减。

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

于 2012-09-28T23:16:03.540 回答
1

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

但我将您引导至'Partition' 上的 Wikipedia 条目，其中还包括一个递归公式。

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

于 2012-09-28T13:45:46.263 回答
1

我认为它需要另一个参数（可以构成分区的整数，称为它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
于 2012-09-28T15:24:28.077 回答
0

您可以使用以下内部函数 - 您只需要创建一个列表，其中的数字<您要分区的数字。比如你要分区4，那么intNumber应该是(1,2,3,4)

  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)
于 2012-09-28T14:10:49.247 回答