CODEWITHSUNDEEP
rubyarraysalgorithm
MrPizzaFace
MrPizzaFace

Reputation: 8086

Generating combinations from an array which == a specified amount?

I need to get all the possible number combinations from denom_arr which equal the amt.

denom_arr = [4,3,1]
amt = 10

This case would produce:

  1. [4, 4, 1, 1]
  2. [3, 3, 3, 1]
  3. [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  4. [4, 3, 1, 1, 1]
  5. [4, 3, 3]
  6. . . . (other cases...)

Problem is the code I wrote is breaking after 1-3 and I'm not sure how to make it loop over the same index to get case 4-6+

set, sets = [], []
i = 0
loop do
i = 0 if denom_arr[i].nil? 

  loop do
    set << denom_arr[i]
    break if set.inject(:+) > amt
  end

  set.pop if set.inject(:+) > amt

  if set.inject(:+) == amt
    sets << set
    set = []
    denom_arr.shift
  end

i += 1
sets
break if denom_arr.empty?
end

UPDATE

I know this can be done with recursion with memoization/dynamic programming techniques, but I am trying to do this strictly in a loop for the sake of testing a theory.

Upvotes: 1

Views: 90

Answers (1)

amnn
amnn

Reputation: 3716

I would do this recursively

def possible_sums(arr, amt)
  return [[]] if amt == 0
  return []   if amt < 0

  arr.reduce([]) do |sums, e|
    sums.concat(
      possible_sums(arr, amt-e)
        .map { |sum| sum.unshift(e).sort }
    )
  end.uniq
end

p possible_sums([4,3,1], 10)
  # => [
  #      [1, 1, 4, 4], [3, 3, 4], [1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 4], 
  #      [1, 3, 3, 3], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 3], 
  #      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  #    ]

Although this is potentially inefficient in that it repeats work, this can be alleviated by using dynamic programming (essentially, memoizing the results of the recursive function).

UPDATE Here is an iterative solution:

def possible_sums_it(arr, amt)
  sums = Array.new(amt+1) { [] }
  sums[0] << []

  (1..amt).each do |i|
    arr.each do |e|
      if i-e >= 0
        sums[i].concat(
          sums[i-e].map { |s| [e, *s].sort }
        )
      end
    end

    sums[i].uniq!
  end

  sums[amt]
end

This is in fact the dynamic programming algorithm for the problem.

So if you squint at it just right, you'll see that essentially what it is doing, is calculating all the possible sums for 0 up to amt into the sums array, using what is basically the recursive algorithm, but instead of the recursive call, we lookup a value in sums that we have calculated beforehand.

This works because we know that we won't need sums[i] before sums[j] for j < i.

Upvotes: 5

Related Questions