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?

Thanks.

Sam