Project Euler 76 - 列出给定编号的所有分区

Question

以下是Project Euler Problem #76 听起来像： “一百可以有多少种不同的方式写成至少两个正整数的和？”

我花了几天的时间努力解决这个问题，尝试以不同的方式解决问题，并且对于小数字（那些易于检查的数字）得到了几乎相同的结果。我最终得到了一种算法，该算法按字母顺序降序列出给定数字的所有分区（从“N-1 + 1”开始）。用 VB.NET 编写：

Dim ub As Integer = 6
Dim wayCount As Integer = 0
For n = ub - 1 To 1 Step -1
  'init value array (first combination)
  Dim s As New List(Of Integer)
  For m = 1 To ub \ n : s.Add(n) : Next
  Dim b As Integer = ub Mod n
  If b <> 0 Then s.Add(b)

  'from where to start decrementing
  Dim k As Integer = s.Count - 1
  While k > 0 And s(k) = 1 : k -= 1 : End While

  Do
    wayCount += 1 : Console.WriteLine(String.Join(" + ", s) & " = " & s.Sum)
    If s(k) = 1 Then k -= 1
    If k = -1 Then Exit Do
    s(k) -= 1
    s.Add(1)
  Loop While k >= 1
Next

Console.WriteLine("count=" & wayCount)

该代码适用于数字 1-6（含），但对于 N=7 则开始失败，缺少 1 个组合。对于 N=8，它会丢失 2 个（19 而不是 21）。对于 N=100，答案是 4576，这比要求的数量级小了几个数量级。显然，我遗漏了一些非常重要的细节。

如果您没有时间或手段来编译和运行上面的代码，这里是输出（N=7）：

6 + 1 = 7
5 + 2 = 7
5 + 1 + 1 = 7
4 + 3 = 7
4 + 2 + 1 = 7
4 + 1 + 1 + 1 = 7
3 + 3 + 1 = 7
3 + 2 + 1 + 1 = 7
3 + 1 + 1 + 1 + 1 = 7
2 + 2 + 2 + 1 = 7
2 + 2 + 1 + 1 + 1 = 7
2 + 1 + 1 + 1 + 1 + 1 = 7
1 + 1 + 1 + 1 + 1 + 1 + 1 = 7
count=13

我已经研究了这些链接：

(ProjectEuler) Sum Combinations - 提供数学解决方案，不列出所有组合

生成数字的分区 - 在 python 中，我无法读取/运行/理解。

任何帮助将不胜感激，提前致谢！

Answer 1

不管你信不信，这个问题有一个相当准确的封闭式解决方案。

哈代和拉马努金公式：

                    e^(PI sqrt(2n/3))
            p(n) ~   -----------------
                        4n sqrt(3)

当 n-> 无穷大时，该公式变得更接近。
数学家拉德马赫（Rademacher）制定了一个精确的公式，但它并不漂亮。
这是一个讨论。

我建议阅读维基百科和 Mathworld 此处和此处。

这是该问题的 MathOverflow 讨论。

我并不是说这些是解决这个问题的最佳方案。事实上，对于相当小的 n 值，它们是浪费时间，但看到这个解决方案以及更“面向计算机”的解决方案很有趣。

Answer 2

正如所承诺的，这里有一些代码使用 N 以内的自然数（但不包括它）对 N（存储在 ub 中）进行分区。经过轻微修改，它应该能够按任何函数进行分区，包括具有浮点输出的函数。

基本思想是，对于分区中使用的每个值，我们都使用系数桶，它是该值的乘数。在每一步中，我们要么将值充电到最大可用值，要么向左或向右移动，递减当前乘数并测试是否达到总和。一旦 sum 成功分区， wayCount 就会递增，结果将打印到屏幕上。

这可能是一个有点脏的实现，但即使对于所讨论的问题范围来说，它也能在合理的时间内工作（在我的机器上不到 5 分钟），每秒生成数百万个分区。永远欢迎健康的批评！

Dim ub As Integer = 10
Dim availableIncrements(ub - 2) As Integer
Dim weightCoefficients(ub - 2) As Integer
For i = 0 To ub - 2
  availableIncrements(i) = ub - i - 1
  weightCoefficients(i) = -1 'indicates that enumeration has not started yet
Next
Dim wayCount As Integer = 0

Dim pos, sum As Integer
pos = 0 : sum = 0
Do
  If weightCoefficients(pos) = -1 Then
    'when we came here first, charge coefficient to maximum available
    weightCoefficients(pos) = (ub - sum) \ availableIncrements(pos)
  ElseIf weightCoefficients(pos) > 0 Then
    'regular cycle: decrease by one
    weightCoefficients(pos) -= 1
  Else
    'return to previous bucket
    If pos = 0 Then Exit Do
    pos -= 1
    Continue Do
  End If

  'calculate current sum
  sum = 0
  For k = 0 To pos
    sum += availableIncrements(k) * weightCoefficients(k)
  Next
  'found combination
  If sum = ub And weightCoefficients(pos) > 0 Then
    wayCount += 1

    'printing to screen, remove when expecting many combinations
    Dim printList As New List(Of Integer)
    For i = 0 To pos 'which number to print
      For k = 1 To weightCoefficients(i) 'how many times to print a number
        printList.Add(availableIncrements(i))
      Next
    Next
    Console.WriteLine(String.Join(" + ", printList))

    'if we were in the last bucket and we just partitioned the number,
    'no need to go down and check all lower coefficients, instead move one column back.
    If pos = UBound(availableIncrements) Then
      pos -= 1
      Continue Do
    End If
  End If

  If pos < UBound(availableIncrements) Then
    pos += 1
    weightCoefficients(pos) = -1 'prepare to charge
  End If

  'this is something to keep you busy (so you know it's not hanging)
  'uncomment for long enumerations
  'If wayCount Mod 100000 = 0 Then Console.WriteLine(wayCount)
Loop

Console.WriteLine("count=" & wayCount)

Answer 3

您说：“该代码适用于数字 1-6（含），但对于 N=7 则开始失败，漏掉了 1 个组合。”对于 N=7，您应该在调试器中或手动单步调试代码。通过详细查看您的代码正在执行的操作，您将能够看到它在哪里遗漏了组合。