Is there an algorithm to find all the combinations of addends for a sum, from a given range of addends which are greater than 1?

user_13991261 0
Viewed 133

I'm trying to create a program that takes a given sum and a given range of allowed addends and outputs the unique configurations of those addends which add up to the sum.

The use case is determining the possible combinations of different-sized multi-member districts to divide the members of a legislature into.

In a trivial example, given 15 legislators, and districts of minimum 3 and maximum 5 seats per district, the possible combinations are:

  • [3, 3, 3, 3, 3]
  • [4, 4, 4, 3]
  • [5, 4, 3, 3]
  • [5, 5, 5]

My initial thought was to start with the largest group of minimum-sized districts possible in a nested array, and add more entries by copying and modifying the previous entry. I don't know how to implement that approach, but I'm also not sure if it's even the right approach to this problem and I'm looking for suggestions.

def multi_member_districts

  reps = 19
  min = 3
  max = 6

  quomin, modmin = reps.divmod(min)
  quomax, modmax = reps.divmod(max)

  groups = Array.new(1) {Array.new}

  (quomin - 1).times do groups[0].push(min) end
  groups[0].unshift(min + modmin)

# PSEUDOCODE
# copy groups[i], insert copy at groups[i+1]
# remove the smallest element of groups[i+1] and spread it out across the other
#   numbers in groups[i+1] in all configurations in which no element exceeds max
# check that there are no duplicate configurations
# repeat

  puts "\nThe possible groups of districts are as follows:"
  groups.each_index do |i|
    (min..max).each do |j|
      unless groups[i].count(j) == 0
        puts ">> #{groups[i].count(j)} #{j}-member districts"
      end
    end
    puts
    puts "o-o-o-o-o-o-o-o-o-o-o-o-o-o"
  end
end

multi_member_districts

EDIT_1: A less trivial example, 19 legislators, 3-6 seats per district --

  • [4, 3, 3, 3, 3, 3]
  • [4, 4, 4, 4, 3]
  • [5, 5, 5, 4]
  • [5, 4, 4, 3, 3]
  • [5, 5, 3, 3, 3]
  • [6, 5, 5, 3]
  • [6, 4, 3, 3, 3]
  • [6, 5, 4, 4]
  • [6, 6, 4, 3]

EDIT_2: Clarified my question, cut down the code, hopefully more suitable

combinatorics ruby
1 Answers

Let's first compute the combinations where each combination corresponds to an array arr where arr[i] equals the number of legislators assigned to district i. If, for example, there are 15 legislators and there must be between 3 and 5 assigned to each district, [3,3,4,5] and [5,3,4,3] would be distinct combinations. We can solve that problem using recursion.

def doit(nbr, rng)
  return nil if nbr < rng.begin
  recurse(nbr, rng)
end

def recurse(nbr, rng)
  (rng.begin..[rng.end, nbr].min).each_with_object([]) do |n,arr|
    if n == nbr
      arr << [n]
    elsif nbr-n >= rng.begin
      recurse(nbr-n, rng).each { |a| arr << a.unshift(n) }
    end
  end
end

doit(15, 3..5)
  #=> [[3, 3, 3, 3, 3], [3, 3, 4, 5], [3, 3, 5, 4], [3, 4, 3, 5],
  #    [3, 4, 4, 4], [3, 4, 5, 3], [3, 5, 3, 4], [3, 5, 4, 3], [4, 3, 3, 5],
  #    [4, 3, 4, 4], [4, 3, 5, 3], [4, 4, 3, 4], [4, 4, 4, 3], [4, 5, 3, 3],
  #    [5, 3, 3, 4], [5, 3, 4, 3], [5, 4, 3, 3], [5, 5, 5]]

doit(19, 3..6)          
  #=> [[3, 3, 3, 3, 3, 4], [3, 3, 3, 3, 4, 3], [3, 3, 3, 4, 3, 3],
  #    [3, 3, 3, 4, 6], [3, 3, 3, 5, 5], [3, 3, 3, 6, 4], [3, 3, 4, 3, 3, 3],
  #    ...
  #    [6, 5, 3, 5], [6, 5, 4, 4], [6, 5, 5, 3], [6, 6, 3, 4], [6, 6, 4, 3]]
doit(19, 3..6).size          
  #=> 111

The question is not concerned, however, with allocations to specific districts. To obtain the combinations of interest we may therefore write the following.

require 'set'

def really_doit(nbr, rng)
  doit(nbr, rng).map(&:tally).uniq.map do |h|
    h.flat_map { |k,v| [k]*v }.sort.reverse
  end                    
end

really_doit(15, 3..5)
  #=> [[3, 3, 3, 3, 3], [5, 4, 3, 3], [4, 4, 4, 3], [5, 5, 5]] 

really_doit(19, 3..6)
  #=> [[4, 3, 3, 3, 3, 3], [6, 4, 3, 3, 3], [5, 5, 3, 3, 3],
  #    [5, 4, 4, 3, 3], [4, 4, 4, 4, 3], [6, 6, 4, 3], [6, 5, 5, 3],
  #    [6, 5, 4, 4], [5, 5, 5, 4]]

Enumerable#tally made its debut in Ruby v2.7. To support earlier versions replace map(&:tally) with map { |a| a.each_with_object(Hash.new(0)) { |n,h| h[n] += 1 }.

Note that doit(nbr, rng).map(&:tally).uniq in returns

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

in really_doit(15, 3..5) and

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

in really_doit(19, 3..6).

We can improve on this by constructing sets of hashes (rather than arrays of arrays) in recurse:

require 'set'

def doit(nbr, rng)
  return nil if nbr < rng.begin
  recurse(nbr, rng).map { |h| h.flat_map { |k,v| [k]*v }.sort.reverse }
end

def recurse(nbr, rng)
  (rng.begin..[rng.end, nbr].min).each_with_object(Set.new) do |n,st|
    if n == nbr
      st << { n=>1 }
    elsif nbr-n >= rng.begin
      recurse(nbr-n, rng).each { |h| st << h.merge(n=>h[n].to_i+1 ) }
    end
  end
end

doit(15, 3..5)
  #=> [[3, 3, 3, 3, 3], [5, 4, 3, 3], [4, 4, 4, 3], [5, 5, 5]] 
doit(19, 3..6)          
  #=> [[4, 3, 3, 3, 3, 3], [6, 4, 3, 3, 3], [5, 5, 3, 3, 3],
  #    [5, 4, 4, 3, 3], [4, 4, 4, 4, 3], [6, 6, 4, 3], [6, 5, 5, 3],
  #    [6, 5, 4, 4], [5, 5, 5, 4]]

Note that here recurse(nbr, rng) in doit returns:

#<Set: {{3=>5}, {5=>1, 4=>1, 3=>2}, {4=>3, 3=>1}, {5=>3}}>

When executing doit(19, 3..6) recurse(nbr, rng) in doit returns:

#<Set: {{4=>1, 3=>5}, {6=>1, 4=>1, 3=>3}, {5=>2, 3=>3},
#       {5=>1, 4=>2, 3=>2}, {4=>4, 3=>1}, {6=>2, 4=>1, 3=>1},
#       {6=>1, 5=>2, 3=>1}, {6=>1, 5=>1, 4=>2}, {5=>3, 4=>1}}>
user_2569700
Related