On 1/22/07, Sam Kong <sam.s.kong / gmail.com> wrote:
> Hi,
>
> I have a question which is not necessarily a ruby-related one.
> Anyway, I'm using Ruby for it.
>
> 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
>
>
> In array form, you may express it like:
>
> [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?
> For example,
>
> set(5) #=> [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1]]
>
> I came up with a mutual recursive solution but it's not very efficient.
> (Probably because it's recursive, which Ruby is not very good at.)
> I can't make it efficient for big numbers.
> I tried to use a cache but it didn't help much enough.
>
> def set n
>   return [[1, 1]] if n == 2
>   result = []
>   (1...n).each do |i|
>     subset = get_subset(n - i, i)
>     subset.each do |j|
>       result << [i] + j
>     end
>   end
>   result
> end
>
> def get_subset n, max
>   result = (n <= max) ? [[n]] : []
>   result += (set(n).select { |i| i.all? { |j| j <= max } })
> end
>
>
> Do you know a good solution to this problem?
> Also, is there a mathematical or algorithmic term for this problem like
> combinations and permutations?

There are a few terms: partition function, number partitioning,
integer partition,...

There is a moderately large literature on the topic.  Try googling.
Wikipedia has some good introductory articles, like
<http://en.wikipedia.org/wiki/Integer_partition>, and a number of
references.

>
> Thanks.
>
> Sam
>
>
>


-- 
Stuart Yarus

<syarus at gmail dot com>