From: James Edward Gray II <james@...>
Date: 2007-01-23T23:13:15+09:00
Subject: Re: I need a more efficient algorithm for this problem.

On Jan 22, 2007, at 11:10 PM, Sam Kong wrote:

> To make 5 by adding 2 more more natural numbers, there are different 6
> ways.
>
> 1 + 1 + 1 + 1 + 1
> 2 + 1 + 1 + 1
> 2 + 2 + 1
> 3 + 1 + 1
> 3 + 2
> 4 + 1

> Is there a general and efficient way to get the arrays?

You said you have a recursive solution.  The first step to optimizing  
recursion is to make sure you aren't doing a bunch of unneeded work.   
For example, generating all the combinations and then removing  
duplicates is too much work.  Instead, we want to make sure we  
recursively generate just one set of numbers:

def partition(largest, rest = Array.new, &block)
   block.call([largest] + rest)
   (rest.first || 1).upto(largest / 2) do |i|
     partition(largest - i, [i] + rest, &block)
   end
end

partition(5) { |nums| p nums }
# >> [5]
# >> [4, 1]
# >> [3, 1, 1]
# >> [2, 1, 1, 1]
# >> [1, 1, 1, 1, 1]
# >> [2, 2, 1]
# >> [3, 2]

The optimization for recursion is to eliminate the recursion.  You  
can always unroll recursive code into an iterative solution:

def partition(num)
   partitions = [[num]]

   until partitions.empty?
     current = partitions.shift

     yield current

     largest = current.shift
     (current.first || 1).upto(largest / 2) do |i|
       partitions << Array[largest - i, i, *current.dup]
     end
   end
end

partition(5) { |nums| p nums }
# >> [5]
# >> [4, 1]
# >> [3, 2]
# >> [3, 1, 1]
# >> [2, 2, 1]
# >> [2, 1, 1, 1]
# >> [1, 1, 1, 1, 1]

I translated these examples from the book Higher-Order Perl and, in  
case you are curious, wrote more about them here:

http://blog.grayproductions.net/articles/2006/01/31/iterators- 
chapters-4-and-5

Hope that helps.

James Edward Gray II