given n, how to find the number of different ways to write n as the sum of 1, 3, 4 in ruby？

Question

Problem: given n, find the number of different ways to write n as the sum of 1, 3, 4 Example:for n=5, the answer is 6

 5=1+1+1+1+1
 5=1+1+3
 5=1+3+1
 5=3+1+1
 5=1+4
 5=4+1

I have tried with permutation method,but its efficiency is very low,is there a more efficient way to do？

Answer 1

Using dynamic programming with a lookup table (implemented with a hash, as it makes the code simpler):

nums=[1,3,4]
n=5

table={0=>1}
1.upto(n) { |i|
  table[i] = nums.map { |num| table[i-num].to_i }.reduce(:+)
}
table[n]
# => 6

Note: Just checking one of the other answers, mine was instantaneous for n=500.

Answer 2

def add_next sum, a1, a2
  residue = a1.inject(sum, :-)
  residue.zero? ? [a1] : a2.reject{|x| residue < x}.map{|x| a1 + [x]}
end

a = [[]]
until a == (b = a.flat_map{|a| add_next(5, a, [1, 3, 4])})
  a = b
end

a:

[
  [1, 1, 1, 1, 1],
  [1, 1, 3],
  [1, 3, 1],
  [1, 4],
  [3, 1, 1],
  [4, 1]
]

a.length #=> 6

Answer 3

I believe this problem should be addressed in two steps.

Step 1

The first step is to determine the different numbers of 1s, 3s and 4s that sum to the given number. For n = 5, there are only 3, which we could write:

[[5,0,0], [2,1,0], [1,0,1]]

These 3 elements are respectively interpreted as "five 1s, zero 3s and zero 4s", "two 1s, one 3 and zero 4s" and "one 1, zero 3s and one 4".

To compute these combinations efficiently, I first I compute the possible combinations using only 1s, that sum to each number between zero and 5 (which of course is trivial). These values are saved in a hash, whose keys are the summands and the value is the numbers of 1's needed to sum to the value of the key:

h0 = { 0 => 0, 1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5 }

(If the first number had been 2, rather than 1, this would have been:

h0 = { 0 => 0, 2 => 1, 4 => 2 }

since there is no way to sum only 2s to equal 1 or 3.)

Next we consider using both 1 and 3 to sum to each value between 0 and 5. There are only two choices for the number of 3s used, zero or one. This gives rise to the hash:

h1 = { 0 => [[0,0]], 1 => [[1,0]], 2 => [[2,0]], 3 => [[3,0], [0,1]],
  4 => [[4,0], [1,1]], 5 => [[5,0], [2,1]] }

This indicates, for example, that:

• there is only 1 way to use 1 and 3 to sum to 1: 1 => [1,0], meaning one 1 and zero 3s.
• there are two ways to sum to 4: 4 => [[4,0], [1,1]], meaning four 1s and zero 3s or one 1 and one 3.

Similarly, when 1, 3 and 4 can all be used, we obtain the hash:

h2 = { 5 => [[5,0,0], [2,1,0], [1,0,1]] }

Since this hash corresponds to the use of all three numbers, 1, 3 and 4, we are concerned only with the combinations that sum to 5.

In constructing h2, we can use zero 4s or one 4. If we use use zero 4s, we would use one 1s and 3s that sum to 5. We see from h1 that there are two combinations:

5 => [[5,0], [2,1]]

For h2 we write these as:

[[5,0,0], [2,1,0]]

If one 4 is used, 1s and 3s totalling 5 - 1*4 = 1 are used. From h1 we see there is just one combination:

1 => [[1,0]]

which for h2 we write as

[[1,0,1]]

so

the value for the key 5 in h2 is:

[[5,0,0], [2,1,0]] + [[1,0,1]] = [[5,0,0], [2,1,0]], [1,0,1]]  

Aside: because of form of hashes I've chosen to represent hashes h1 and h2, it is actually more convenient to represent h0 as:

h0 = { 0 => [[0]], 1 => [[1]],..., 5 => [[5]] }  

It should be evident how this sequential approach could be used for any collection of integers whose combinations are to be summed.

Step 2

The numbers of distinct arrangements of each array [n1, n3, n4] produced in Step 1 equals:

(n1+n3+n4)!/(n1!n3!n4!)

Note that if one of the n's were zero, these would be binomial coefficients. If fact, these are coefficients from the multinomial distribution, which is a generalization of the binomial distribution. The reasoning is simple. The numerator gives the number of permutations of all the numbers. The n1 1s can be permuted n1! ways for each distinct arrangement, so we divide by n1!. Same for n3 and n4

For the example of summing to 5, there are:

• 5!/5! = 1 distinct arrangement for [5,0,0]
• (2+1)!/(2!1!) = 3 distinct arrangements for [2,1,0] and
• (1+1)!/(1!1!) = 2 distinct arrangements for [1,0,1], for a total of:

1+3+2 = 6 distinct arrangements for the number 5.

Code

def count_combos(arr, n)
  a = make_combos(arr,n)
  a.reduce(0) { |tot,b| tot + multinomial(b) }
end

def make_combos(arr, n)
  arr.size.times.each_with_object([]) do |i,a|
    val = arr[i]
    if i.zero?
      a[0] = (0..n).each_with_object({}) { |t,h|
        h[t] = [[t/val]] if (t%val).zero? }
    else
      first = (i==arr.size-1) ? n : 0 
      a[i] = (first..n).each_with_object({}) do |t,h|
        combos = (0..t/val).each_with_object([]) do |p,b|
          prev = a[i-1][t-p*val]
          prev.map { |pr| b << (pr +[p]) } if prev
        end
        h[t] = combos unless combos.empty?
      end    
    end
  end.last[n]
end

def multinomial(arr)
  (arr.reduce(:+)).factorial/(arr.reduce(1) { |tot,n|
    tot * n.factorial })
end  

and a helper:

class Fixnum
  def factorial
    return 1 if self < 2
    (1..self).reduce(:*)
  end
end

Examples

count_combos([1,3,4], 5)     #=> 6
count_combos([1,3,4], 6)     #=> 9
count_combos([1,3,4], 9)     #=> 40
count_combos([1,3,4], 15)    #=> 714
count_combos([1,3,4], 30)    #=> 974169
count_combos([1,3,4], 50)    #=> 14736260449
count_combos([2,3,4], 50)    #=> 72581632   
count_combos([2,3,4,6], 30)  #=> 82521
count_combos([1,3,4], 500)   #1632395546095013745514524935957247\
  00017620846265794375806005112440749890967784788181321124006922685358001

(I broke the result the example (one long number) into two pieces, for display purposes.)

count_combos([1,3,4], 500) took about 2 seconds to compute; the others were essentially instantaneous.

@sawa's method and mine gave the same results for n between 6 and 9, so I'm confident they are both correct. sawa's solution times increase much more quickly with n than do mine, because he is computing and then counting all the permutations.

Edit: @Karole, who just posted an answer, and I get the same results for all my tests (including the last one!). Which answer do I prefer? Hmmm. Let me think about that.)

Answer 4

I don't know ruby so I am writing it in C++ say for your example n=5. Use dynamic programming set

int D[n],n;
cin>>n;
D[0]=1;
D[1]=1;
D[2]=1;
D[3]=2; 
for(i = 4; i <= n; i++)
    D[i] = D[i-1] + D[i-3] + D[i-4];
cout<<D[i];