a repeated permutation with limitations

Question

I am trying to generate all possible combinations of certain values in an array of 15 which add up to 50.

$a = [3, 4, 1, 2, 5]
print $a.repeated_permutation(15).to_a

In this case,

[2,2,2,2,4,4,4,4,4,4,4,4,4,3,3]
[2,2,2,4,2,4,4,4,4,4,4,4,4,3,3]
[2,2,4,2,2,4,4,4,4,4,4,4,4,3,3]

are all possible answers.

After some investigation I realize the code to do this is a bit over my head, but I will leave the question up if it might help someone else.

For some reference as to what I am working on, Project Euler, problem 114. It's pretty difficult, and so I am attempting to solve only a single case where my 50-space-long grid is filled only with 3-unit-long blocks. The blocks must be separated by at least one blank, so I am counting the blocks as 4. This (with some tweaking, which I have left out as this is confusing enough already) allows for twelve blocks plus three single blanks, or a maximum of fifteen elements.

Answer 1

Approach

I think recursion is the way to go here, where your recursive method looks like this:

def recurse(n,t)

where

• n is the number of elements required; and
• t is the required total.

If we let @arr be the array of integers you are given, recurse(n,t) returns an array of all permutations of n elements from @arr that sum to t.

Assumption

I have assumed that the elements of @arr are non-negative integers, sorted by size, but the method can be easily modified if it includes negative integers (though performance will suffer). Without loss of generality, we can assume the elements of @arr are unique, sorted by increasing magnitude.

Code

def recurse(n,t)
  if n == 1
    @arr.include?(t) ? [[t]] : nil
  else
    @arr.each_with_object([]) do |i,a|
      break if i > t # as elements of @arr are non-decreasing
      if (ret = recurse(n-1,t-i))
        ret.each { |b| a << [i,*b] }
      end
    end
  end
end

Examples

@arr = [3, 4, 1, 2, 5].sort
  #=> [1, 2, 3, 4, 5]

recurse(1,4)
  #=> [[4]]
recurse(2,6)
  #=> [[1, 5], [2, 4], [3, 3], [4, 2], [5, 1]] 
recurse(3,10)
  #=> [[1, 4, 5], [1, 5, 4], [2, 3, 5], [2, 4, 4], [2, 5, 3],
  #    [3, 2, 5], [3, 3, 4], [3, 4, 3], [3, 5, 2], [4, 1, 5],
  #    [4, 2, 4], [4, 3, 3], [4, 4, 2], [4, 5, 1], [5, 1, 4],
  #    [5, 2, 3], [5, 3, 2], [5, 4, 1]] 
recurse(3,50)
  #=> [] 

Improvement

We can do better, however, by first computing all combinations, and then computing the permutations of each of those combinations.

def combo_recurse(n,t,last=0)
    ndx = @arr.index { |i| i >= last }
    return nil if ndx.nil?
    arr_above = @arr[ndx..-1] 
  if n == 1
    arr_above.include?(t) ? [[t]] : nil
  else
    arr_above.each_with_object([]) do |i,a|
      break if i > t # as elements of @arr are non-decreasing
      if (ret = combo_recurse(n-1,t-i,i))
        ret.each { |b| a << [i,*b] }
      end
    end
  end
end

combo_recurse(1,4)
  #=> [[4]]
combo_recurse(2,6)
  #=> [[1, 5], [2, 4], [3, 3]] 
combo_recurse(3,10)
  #=> [[1, 4, 5], [2, 3, 5], [2, 4, 4], [3, 3, 4]] 
combo_recurse(3,50)
  #=> [] 
combo_recurse(15,50).size
  #=> 132 
combo_recurse(15,50).first(5)
  #=> [[1, 1, 1, 1, 1, 1, 4, 5, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 2, 4, 4, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5],
  #    [1, 1, 1, 1, 1, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5]] 

We can then compute the permutations from the combinations:

combo_recurse(2,6).flat_map { |a| a.permutation(a.size).to_a }.uniq
  #=> [[1, 5], [5, 1], [2, 4], [4, 2], [3, 3]] 
combo_recurse(3,10).flat_map { |a| a.permutation(a.size).to_a }.uniq
  #=> [[1, 4, 5], [1, 5, 4], [4, 1, 5], [4, 5, 1], [5, 1, 4],
  #    [5, 4, 1], [2, 3, 5], [2, 5, 3], [3, 2, 5], [3, 5, 2],
  #    [5, 2, 3], [5, 3, 2], [2, 4, 4], [4, 2, 4], [4, 4, 2],
  #    [3, 3, 4], [3, 4, 3], [4, 3, 3]] 

We can approximate the number of permutations for (15,50) (it will be somewhat high because uniq is not applied):

def factorial(n)
  (1..n).reduce :*
end

Math.log10 combo_recurse(15,50).reduce(1) { |t,a| t*factorial(a.size) }
  #=> 1599.3779486682888 

That is, the result has about 1,600 digits. What platform will you be running this on?