与えられた整数をmaxを超えない範囲で均等に分割する

Question

解決したい問題

ある数(total)を最大値(max)を超えない範囲で分割したい

• total,maxは正の整数
• 分割数はtotal/max以上の最小の整数
• 分割後の要素の分散が最小になる
• 順序は問わず

function(53, 25)

# OK
[18, 18, 17]
[18, 17, 18]
[17, 18, 18]


# NG
[25, 25, 3]
[1, 1, 1, 1, ...., 1]

以下は自分で書いたコードですがいまいちな感じでもっと良い書き方アルゴリズムがあったら教えてください。言語は問いません。

# 与えられた整数をmaxを超えない範囲で均等に分割する
# @param [Integer] total - 分割対象となる値 正の整数
# @param [Integer] max - 分割される際の最大値 正の整数
# @return [Array<Integer>]
def distribute_evently(total, max)
  length = total.fdiv(max).ceil
  base = total / length
  remain = total - (base * length)

  Array.new(length, base).map do |n|
    if remain > 0
      remain -= 1
      n + 1
    else
      n
    end
  end
end

Comments

[ozwk]

何を以って「均等」としますか?分散を最小にするんですか?評価基準を教えてください。

[退会済みユーザー]

"分散を最小にするんですか" はいそうです。結果の配列の要素の分散が最小になるようにしたいです、順序は問いません。

[ozwk]

そうすると1をtotal個が最適になりますが?

[退会済みユーザー]

確かにそうですね。「結果の配列の長さを最小にしたうえで、要素の分散が最小になるように。順序は問わず」かな。

[ozwk]

評価基準が2つあると重みづけの問題が出てきます。おそらくですが、分割数はtotal/max以上の最小の整数という制限を意図していませんか?

[退会済みユーザー]

"分割数はtotal/max以上の最小の整数という制限を意図していませんか" はいそのとおりです。

[ozwk]

distribute_evently(53, 25)の結果は[18,18,17]では?

[退会済みユーザー]

おっと、失礼しました。修正しておきます。

Answer 1

def distribute_evently(total, max)
  length = total.fdiv(max).ceil
  base = total / length
  remain = total - (base * length)
  Array.new(length-remain, base).concat(Array.new(remain, base+1))
end

p distribute_evently(10,3) # [2,2,3,3]
p distribute_evently(53,25)# [17,18,18]

Comments

[退会済みユーザー]

`Array.new(length-remain, base).concat(Array.new(remain, base+1))` 「綺麗なロジックだなあ」と感心させられました、ありがとうございます。