20724

Project Euler 76 - List All Partitions For a Given Number

Question:

Here is how <a href="http://projecteuler.net/index.php?section=problems&id=76" rel="nofollow" title="original problem description">Project Euler Problem #76</a> 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:

<a href="https://stackoverflow.com/questions/438540/projecteuler-sum-combinations" rel="nofollow">(ProjectEuler) Sum Combinations</a> - provides a mathematical solution, which does not list all combinations

<a href="https://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number" rel="nofollow">Generating the partitions of a number</a> - is in python, which I cannot read/run/understand.

Any help would be much appreciated, thanks in advance!

Answer1:

You say, "The code works for numbers 1-6 inclusive and starts failing for N=7, with 1 combination missed." You should step through your code one line at a time for N=7, either in a debugger or by hand. By seeing in detail exactly what your code is doing you will be able to see where it misses a combination.

Answer2:

There is a fairly accurate closed-form solution to this problem, believe it or not.

Hardy and Ramanujan's formula:

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

which gets closer as n->infinity. The mathematician Rademacher made an exact formula, but it isn't pretty. <a href="http://users.math.yale.edu/~alf8/Folsom-Masri-MathAnn07-10.pdf" rel="nofollow">Here's a discussion.</a>

I would recommend reading about it on Wikipedia and Mathworld <a href="http://mathworld.wolfram.com/PartitionFunctionP.html" rel="nofollow">here</a> and <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function" rel="nofollow">here</a>.

<a href="https://mathoverflow.net/questions/47611/exact-formulas-for-the-partition-function" rel="nofollow">This</a> is the MathOverflow discussion of the problem.

I'm not saying these are the best solutions to this problem. In fact for reasonably small values of n they're a waste of time, but it is interesting to see this solution as well as the more "computer-oriented" ones.

Answer3:

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)

Recommend

  • Dreamweaver error warning
  • Doesn't Cassandra perform “late” replication when a node down and up again?
  • Running each child form as a separate thread in a MDI container
  • Is the conversion from '(signed) -1' to 'unsigned long' standardized? [duplicate
  • How to get Bass, Mid, Treble data from FFT
  • In built Elastic Search analyzer which does work of Simple Analyzer as well tokenize the number
  • Selecting and check if user exist in table without foreach in laravel blade
  • Tokenize python source code examples (in Python)
  • Implement a writable serializer for multilevel nested relationships in django rest framework
  • SUM and GROUP BY in xquery with 1 xml file
  • Add the % on tab when working with HAML on vim
  • Difficulties implementing the Hysteresis step of Canny Algorithm in Halide without define_extern fun
  • PyYaml parses '9:00' as int
  • While loop won't end when I tell it in JavaScript
  • Why is it still possible to insert a foreign key that doesn't exist?
  • Implementation of RTTI using typeid
  • NUnit 3.0 TestCase const custom object arguments
  • Does Mobilefirst provide a provision to access web services directly?
  • Groovy: Unexpected token “:”
  • Admob requires api-13 or later can I not deploy on old API-8 phones?
  • java.lang.NoClassDefFoundError: com.parse.Parse$Configuration$Builder on below Lollipop versions
  • Read text file and split every line in MSBuild
  • Does CUDA 5 support STL or THRUST inside the device code?
  • When should I choose bucket sort over other sorting algorithms?
  • How do you troubleshoot character encoding problems?
  • Jquery - Jquery Wysiwyg return html as a string
  • Arrays break string types in Julia
  • Codeigniter doesn't let me update entry, because some fields must be unique
  • WPF Applying a trigger on binding failure
  • Understanding cpu registers
  • Why joiner is not used after Sequence generator or Update statergy
  • Java static initializers and reflection
  • Exception on Android 4.0 `android.os.StrictMode$AndroidBlockGuardPolicy.onNetwork(StrictMode)`
  • Can Visual Studio XAML designer handle font family names with spaces as a resource?
  • File not found error Google Drive API
  • Qt: Run a script BEFORE make
  • How can I remove ASP.NET Designer.cs files?
  • Are Kotlin's Float, Int etc optimised to built-in types in the JVM? [duplicate]
  • Is it possible to post an object from jquery to bottle.py?
  • Does armcc optimizes non-volatile variables with -O0?