将数组分成最小和最大长度的组的最佳Ruby算法是什么？

Question

我有一个背景工作，需要合并很多项目在一起。我想将其拆分为多个“子作业”，每个子作业合并数据的一个子集，然后最后一个过程将所有“子作业”的输出合并在一起。

一种简单的方法是将数据分成x元素组。问题是最后一个组可能有1个元素的剩余部分，因此它将是一个“noop”。我想找到最佳的“x”，这样组就大致相等，并且每个组中有最小和最大数量的元素（例如，不少于10个元素，不超过20个）

在Ruby中有什么好的算法？

以下是一些示例输出，最小为10，最大为20。这些数字表示每个数组中的元素数。

<number of elements in input> => <subgroup 1>, <subgroup 2>, etc. 

5 => 5
10 => 10
15 => 15
20 => 20
21 => 10, 11
30 => 15, 15
40 => 20, 20
41 => 13, 14, 14
42 => 14, 14, 14
43 => 14, 14, 15
45 => 15, 15, 15
50 => 16, 17, 17
55 => 18, 18, 19
60 => 20, 20, 20
61 => 15, 15, 15, 16

基本上，我想把数组分成大致均匀的组，但是每个组中的元素数量最小和最大。

Answer 1

以下是我尝试的解决方案：

class ArrayPartition
  def self.partition_lengths(length, minimum, maximum)
    if length <= maximum
      return [length]
    end

    group_size = maximum
    groups = []

    while groups.empty? || groups.last < minimum
      groups = []
      remaining = length
      while remaining > group_size
        groups << group_size
        remaining -= group_size
      end
      groups << remaining
      group_size -= 1
    end

    # Redistribute evenly
    avg_group_size = (length / groups.size.to_f).round
    groups = []
    remaining = length
    while remaining > maximum
      groups << avg_group_size
      remaining -= avg_group_size
    end
    groups << remaining

    groups.sort
  end
end

RSpec测试：

RSpec.describe ArrayPartition do
  it 'partitions an array into optimal groups with min and max elements' do
    expect(ArrayPartition.partition_lengths(5, 5, 10)).to eq [5]
    expect(ArrayPartition.partition_lengths(6, 5, 10)).to eq [6]
    expect(ArrayPartition.partition_lengths(7, 5, 10)).to eq [7]
    expect(ArrayPartition.partition_lengths(10, 5, 10)).to eq [10]
    expect(ArrayPartition.partition_lengths(11, 5, 10)).to eq [5, 6]
    expect(ArrayPartition.partition_lengths(12, 5, 10)).to eq [6, 6]
    expect(ArrayPartition.partition_lengths(13, 5, 10)).to eq [6, 7]
    expect(ArrayPartition.partition_lengths(16, 5, 10)).to eq [8, 8]
    expect(ArrayPartition.partition_lengths(20, 5, 10)).to eq [10, 10]
    expect(ArrayPartition.partition_lengths(21, 5, 10)).to eq [7, 7, 7]
    expect(ArrayPartition.partition_lengths(22, 5, 10)).to eq [7, 7, 8]

    expect(ArrayPartition.partition_lengths(5, 10, 20)).to eq [5]
    expect(ArrayPartition.partition_lengths(10, 10, 20)).to eq [10]
    expect(ArrayPartition.partition_lengths(15, 10, 20)).to eq [15]
    expect(ArrayPartition.partition_lengths(20, 10, 20)).to eq [20]
    expect(ArrayPartition.partition_lengths(21, 10, 20)).to eq [10, 11]
    expect(ArrayPartition.partition_lengths(30, 10, 20)).to eq [15, 15]
    expect(ArrayPartition.partition_lengths(40, 10, 20)).to eq [20, 20]
    expect(ArrayPartition.partition_lengths(41, 10, 20)).to eq [13, 14, 14]
    expect(ArrayPartition.partition_lengths(42, 10, 20)).to eq [14, 14, 14]
    expect(ArrayPartition.partition_lengths(43, 10, 20)).to eq [14, 14, 15]
    expect(ArrayPartition.partition_lengths(45, 10, 20)).to eq [15, 15, 15]
    expect(ArrayPartition.partition_lengths(50, 10, 20)).to eq [16, 17, 17]
    expect(ArrayPartition.partition_lengths(55, 10, 20)).to eq [18, 18, 19]
    expect(ArrayPartition.partition_lengths(60, 10, 20)).to eq [20, 20, 20]
    expect(ArrayPartition.partition_lengths(61, 10, 20)).to eq [15, 15, 15, 16]
  end
end

Answer 2

稍有不同的版本：

def divide(c, max = 20)
  groups = (c.to_f / max).ceil
  min_count = (c.to_f / groups).floor

  [min_count + 1] * (c % min_count) + [min_count] * (groups - c % min_count)
end

Answer 3

我会这样处理：

# count of original items
count = 61

# max bucket size
max = 20

# decide buckets
groups = (count / max) + (count % max > 0 ? 1 : 0)

# this will be the final result
result = []

# create buckets
groups.times { result.push(0) }

# iterate over original items and distribute them in the buckets
count.times do |n|
  result[n % groups] += 1
end

p result

给定Count为61，它会打印16, 15, 15, 15。我已经在代码片段中解释了每个语句的目的。