From: Sam Kong <sam.s.kong@...>
Date: 2007-01-23T14:10:06+09:00
Subject: I need a more efficient algorithm for this problem.

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