Hi James,

James Edward Gray II wrote:
> 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:

Right. But some recursions are harder to unroll than others.^^

>
> 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

Your weblog looks very helpful.
I just bookmarked it.

>
> Hope that helps.

Yes. It helped a lot.
>
> James Edward Gray II

Thank you very much.
Also, I thank others who replied to my question.

Sam