Каков наилучший алгоритм Ruby для разделения массива на группы с минимальной и максимальной длиной?

Question

У меня есть фоновая работа, которая должна объединить множество элементов.Я хочу разделить это на несколько «подзадач», каждый из которых объединяет подмножество данных, а затем заключительный проход, который объединяет выходные данные всех «подзадач» вместе.

Наивный способ сделатьэто разделить данные на группы по х элементов.Проблема в том, что в последней группе может быть остаток от 1 элемента, поэтому это будет «noop».Я хочу найти оптимальное «х», чтобы группы были примерно четными и имели минимальное и максимальное количество элементов в каждой группе (например, не менее 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

Я бы подошел к этому так:

# 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. Я объяснил назначение каждого утверждения в самом фрагменте.

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

Вот моя попытка найти решение:

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