项目Euler 76-列出给定数量的所有分区 [英] Project Euler 76 - List All Partitions For a Given Number

问题描述

以下是Project Euler Problem#76的方式听起来像:至少有两个正整数之和，可以用一百种方式写成一百种?"

几天来我一直在努力解决问题，尝试以不同的方式解决问题，并且对于少量数字(易于检查的数字)，结果大致相同.我最终得到了一种算法，该算法按字母顺序列出给定数字的所有分区，然后降序(从"N-1 + 1"开始).用VB.NET编写:

  Dim ub As Integer = 6昏暗wayCount为整数= 0对于n = ub-1至1步骤-1'初始值数组(第一个组合)Dim s作为新列表(整数)对于m = 1到ub \ n:s.Add(n):接下来Dim b As Integer = ub Mod n如果b<>0然后s.Add(b)'从哪里开始递减Dim k As Integer = s.Count-1当k>0并且s(k)= 1:k-= 1:结束时间做wayCount + = 1:Console.WriteLine(String.Join("+"，s&&;"="& s.Sum)如果s(k)= 1那么k-= 1如果k = -1，则退出Dos(k)-= 1s.Add(1)当k> = 1时循环下一个Console.WriteLine("count ="& wayCount) 

该代码适用于1-6(包括1-6)的数字，并且在N = 7时开始失败，缺少1个组合.对于N = 8，它错过2(19而不是21).对于N = 100，答案为4576，比所需数量少几个数量级.显然，我缺少一些非常重要的细节.

如果您没有时间或精力来编译和运行上面的代码，则输出为(N = 7):

  6 +1 = 75 + 2 = 75 +1 +1 = 74 + 3 = 74 + 2 + 1 = 74 +1 +1 +1 = 73 + 3 + 1 = 73 + 2 + 1 + 1 = 73 +1 +1 +1 +1 = 72 + 2 + 2 + 1 = 72 + 2 + 1 + 1 + 1 = 72 +1 +1 +1 +1 +1 = 71 +1 +1 +1 +1 +1 +1 = 7计数= 13 

我研究了以下链接:

(ProjectEuler)Sum Combinations -提供了一种数学解决方案，其中未列出所有组合

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

任何帮助将不胜感激，在此先感谢您！

解决方案

如所承诺的，以下代码使用自然数最多N进行N(存储在ub中)的分区，但不包括N.稍作修改，它应该可以按任何功能进行分区，包括带浮点输出的功能.

基本思想是，对于分区中使用的每个值，我们都使用系数存储桶，它是该值的乘数.在每一步中，我们要么将值收取到最大可用值，要么向左或向右移动，减小电流乘数并测试是否达到总和.成功地对总和进行分区后，wayCount就会增加，并且结果会显示在屏幕上.

这可能是一个有点肮脏的实现，但是即使在有问题的范围内(在我的计算机上不到5分钟)，它也可以在合理的时间内工作，每秒生成数百万个分区.始终欢迎健康的批评！

  Dim ub As Integer = 10Dim availableIncrements(ub-2)作为整数昏暗的weightCoefficients(ub-2)作为整数对于i = 0至ub-2availableIncrements(i)= ub-i-1weightCoefficients(i)= -1'表示枚举尚未开始下一个昏暗wayCount为整数= 0Dim pos，总和为整数pos = 0:总和= 0做如果weightCoefficients(pos)= -1，则'当我们首先来到这里时，充电系数应达到最大weightCoefficients(pos)=(ub-sum)\ availableIncrements(pos)否则，如果weightCoefficients(pos)>0然后'定期循环:减少一倍weightCoefficients(pos)-= 1别的'返回上一个存储桶如果pos = 0，则退出执行pos-= 1继续做万一'计算当前总和总和= 0对于k = 0到pos总和== availableIncrements(k)* weightCoefficients(k)下一个'找到组合如果sum = ub且weightCoefficients(pos)>0然后wayCount + = 1'打印到屏幕上，在期望许多组合时将其移除将printList变暗为新列表(整数)对于i = 0至pos'要打印哪个数字对于k = 1 To weightCoefficients(i)'多少次打印一个数字printList.Add(availableIncrements(i))下一个下一个Console.WriteLine(String.Join("+"，printList))如果我们在最后一个存储桶中，并且只是对数字进行了分区，'无需下降并检查所有较低的系数，而后移一列.如果pos = UBound(availableIncrements)然后pos-= 1继续做万一万一如果pos<UBound(availableIncrements)然后pos + = 1weightCoefficients(pos)= -1'准备充电万一``这会让你很忙(所以你知道它没有挂起来)'对于长时间枚举不建议'如果wayCount Mod 100000 = 0然后Console.WriteLine(wayCount)环形Console.WriteLine("count ="& wayCount) 

Here is how Project Euler Problem #76 sounds like: "How many different ways can one hundred be written as a sum of at least two positive integers?"

I've struggled to get it right for a couple of days, tried to solve in different ways and got mostly the same results for small numbers (those that are easy to check). I ended up with an algorithm that lists all partitions for a given number in alphabetical order, descending (starting from "N-1 + 1"). Written in 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)

The code works for numbers 1-6 inclusive and starts failing for N=7, with 1 combination missed. For N=8 it misses 2 (19 instead of 21). For N=100 the answer is 4576, which is several orders of magnitude less than required. Clearly, I am missing some very important detail.

If you don't have time or means to compile and run the above code, here is the output (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

I've studied these links:

(ProjectEuler) Sum Combinations - provides a mathematical solution, which does not list all combinations

Generating the partitions of a number - is in python, which I cannot read/run/understand.

Any help would be much appreciated, thanks in advance!

解决方案

As promised, here is some code that does partitioning of N (stored in ub) using natural numbers up to N, but not including it. With slight modification, it should be able to partition by any function, including that with floating point output.

Basic idea is that for every value used in partitioning we are using coefficient bucket, which is a multiplier of that value. On every step we either charge the value to maximum available, move left or right, decrement current multiplier and test if we get to the sum. Once sum was successfully partitioned, wayCount is incremented and result is printed to the screen.

This might be a somewhat dirty implementation, but it works in a reasonable time even for the scope of the problem in question (under 5 minutes on my machine), generating several millions of partitions per second. Healthy criticism is always welcome!

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)

这篇关于项目Euler 76-列出给定数量的所有分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！