是否有一种算法可以从给定的大于 1 的加数范围中找到总和的所有加数组合？

Question

我正在尝试创建一个程序，该程序采用给定的总和和给定范围的允许加数，并输出这些加数的独特配置，这些加数加起来等于总和。

用例是确定不同规模的多成员选区的可能组合，以将立法机构的成员划分为。

在一个简单的例子中，给定 15 名立法者，每个选区最少 3 个和最多 5 个席位，可能的组合是：

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

我最初的想法是从嵌套数组中尽可能多的最小区域组开始，然后通过复制和修改先前的条目来添加更多条目。我不知道如何实施这种方法，但我也不确定它是否是解决这个问题的正确方法，我正在寻找建议。

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: 一个不太重要的例子，19 名立法者，每个选区 3-6 个席位 --

[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: 澄清了我的问题，删减代码，希望更合适

Answer 1

让我们首先计算组合，其中每个组合对应一个数组 arr，其中 arr[i] 等于分配给选区 i 的立法者数量。例如，如果有 15 名立法者，并且每个选区必须分配 3 到 5 名议员，则 [3,3,4,5] 和 [5,3,4,3] 将是不同的组合。我们可以使用递归来解决这个问题。

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

然而，问题与特定地区的分配无关。因此，为了获得感兴趣的组合，我们可以编写以下内容。

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 在 Ruby v2.7 中首次亮相。要支持早期版本，请将 map(&:tally) 替换为 map { |a| a.each_with_object(Hash.new(0)) { |n,h| h[n] += 1 }。

请注意 returns

中的 doit(nbr, rng).map(&:tally).uniq

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

在really_doit(15, 3..5)和

[{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}]

在 really_doit(19, 3..6).

我们可以通过在 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]]

注意这里 recurse(nbr, rng) in doit returns:

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

在doit中执行doit(19, 3..6)recurse(nbr, rng)时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}}>

是否有一种算法可以从给定的大于 1 的加数范围中找到总和的所有加数组合？

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?

ruby

combinatorics