お題
長さ n
の配列があるとする。
配列の要素は,まあ何でもいいんだけど,人を表しているとする。
簡単のため,
persons = ["Alice", "Bob", "Carol", "Dan", "Emily", "Finn"]
としよう。
これを均等に m
個に分割したいとする。要する班わけですな。
さきほどの persons
を 3 班に分けるなら,たとえば
[
["Alice", "Bob"],
["Carol", "Dan"],
["Emily", "Finn"]
]
みたいな二重配列が欲しいわけだ。
一般には n
が m
で割り切れるとは限らないので,班によって人数が異なりうる,ということに注意しよう。
その場合でも,なるべく人数が揃うようにしたい。
班の最大人数は ceil(n/m)
なるべく人数が均等になるようにするなら,班の最大人数は
\left\lceil \frac nm \right\rceil
となる。($\lceil\hspace{0.25em}\rceil$ は天井関数というやつで,まあ大雑把には切り上げと思ってもらえばいい)
要するに
- $n$ が $m$ で割り切れるならただの商
- 割り切れないなら整商(整数の商)プラス 1
というわけだ。
たとえば 10 人を 3 班に分ける場合,$\left\lceil \frac{10}{3} \right\rceil = 4$ なので,最大 4 人の班ができる。
Ruby で $\left\lceil \frac nm \right\rceil$ を書くなら
n.quo(m).ceil
とすればよい。
多くの人は
n.fdiv(m).ceil
と書くかもしれないが,整数の問題において中間に浮動小数点数演算を持ち込むのは誤差の発生が怖いので,避けたほうがよい。
Integer 同士の quo
は Rational オブジェクトを返すので,誤差を気にする必要がない。
最大人数ずつ取っていく方法
まず素朴な考え方として,全体を最大人数ずつ切り取っていく,という方法が思い浮かぶ。
この目的には Enumerable#each_slice がうってつけだ。
以下のようになるだろう。
ここでは,A
から J
までの 10 人を 3 班に分けるようにしている。
persons = [*"A".."J"]
p persons # => ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
m = 3 # 班の数
x = persons.length.quo(m).ceil
p x # => 4
groups = persons.each_slice(x).to_a
# => [
# ["A", "B", "C", "D"],
# ["E", "F", "G", "H"],
# ["I", "J"]
# ]
うーむ,これはちょっとな。
10 人を 4 人ずつ切り取ったので,4 人,4 人,2 人になってしまった。
「最大 4 人」は満たされているが,「なるべく均等」にはなっていない。
4 人,3 人,3 人に分けなければいけない。
なお,each_slice
のブロック無し用法では Enumerator オブジェクトが返るので,配列を得るために to_a
してやる必要があった。
トランプ配り
トランプゲームの大富豪や七並べなどで,全カードを全プレイヤーに均等に配るときは,〈全プレイヤーに 1 枚ずつ配る〉ということをカードが尽きるまで繰り返す(もちろん最後だけは全員に行き渡らず途中で尽きることがありうる)。
このやり方であれば,配られたカード枚数の差は最大 1 となる。
たとえばこんなコードになるだろうか。
persons = [*"A".."J"]
m = 3 # 班の数
# 班数ぶんの空配列の配列を用意
groups = Array.new(m){ [] }
persons.each_with_index do |person, i|
groups[i % m] << person
end
p groups
# => [
# ["A", "D", "G", "J"],
# ["B", "E", "H"],
# ["C", "F", "I"]
# ]
(0 始まりのインデックスで)$i$ 番目の人は $i$ を $m$ で割った余り(i % m
)でラベル付けされる班に割り当てる,というわけだ。
トランプ配りをそのまんま Ruby コードにした感じ。
ええと,もうちょっと簡潔に書けないっすかね?
Enumerable#group_by を使おう。
以下のようになる。
persons = [*"A".."J"]
m = 3 # 班の数
groups = persons.group_by.with_index{ |person, i| i % m }.values
p groups
# => [
# ["A", "D", "G", "J"],
# ["B", "E", "H"],
# ["C", "F", "I"]
# ]
Enumerator に慣れていないと,ブロック無し group_by
に with_index
をかますのはちょっと不思議なコードに見えるかもしれない。
k 番目の班に入る人を拾っていく
(以下,「○番目」は全て 0 始まりのインデックスとする)
$k$ 番目の班に入る人のインデックスは,$k$, $k+m$, $k+2m$,... という等差数列になっている。
ならば,等差数列を表す Enumerator::ArithmeticSequence オブジェクトを使って,一網打尽にしてはどうか。
$k$ 番めの班に入るべき人のインデックスは,初項 $k$,公差 $m$ の等差数列(ただし,$n$ 未満)だから,
(k...n).step(m)
で得られる。よって,こう書ける。
persons = [*"A".."J"]
n = persons.length
m = 3 # 班の数
groups = Array.new(m){ |k| persons.values_at(*(k...n).step(m)) }
p groups
# => [
# ["A", "D", "G", "J"],
# ["B", "E", "H"],
# ["C", "F", "I"]
# ]
頭から分けてほしいんですが
ここまでの例では,トランプ配りと同じく,最初の $m$ 要素が全部別々の班に入るように分かれる。
もし,先頭から
[
["A", "B", "C", "D"],
["E", "F", "G"],
["H", "I", "J"]
]
のように分かれてほしいときはどうするか。
$n$ を $m$ で割った整商を $q$,剰余を $r$ とすると,
- 班の最小人数は $q$ 人
- 班の最大人数は,$r=0$ なら $q$ 人,そうでないなら $q+1$ 人
となる。
そして,
- $q+1$ 人の班は $r$ 個
- $q$ 人の班は $m-r$ 個
できる。
これをそのままコードにすればよさそうだ。
整商と剰余を一度に得るには Numeric#divmod が使える。
たとえばこう:
persons = [*"A".."J"]
m = 3 # 班の数
q, r = persons.length.divmod(m)
q1 = q + 1
groups = Array.new(m) do |k|
(k < r) ? persons[q1 * k, q1] : persons[q1 * r + q * (k - r) , q]
end
p groups
# => [
# ["A", "B", "C", "D"],
# ["E", "F", "G"],
# ["H", "I", "J"]
# ]
あるいはこう:
persons = [*"A".."J"]
m = 3 # 班の数
q, r = persons.length.divmod(m)
q1 = q + 1
groups = (persons[0, q1 * r].each_slice(q1) + persons[(q1 * r)..].each_slice(q)).to_a
p groups
# => [
# ["A", "B", "C", "D"],
# ["E", "F", "G"],
# ["H", "I", "J"]
# ]
おわりに
なぜこんな記事を書いたかというと,仕事で書いていたアプリケーションで,配列の均等分割をやる必要があったから。
当初「最大人数ずつ取っていく方法」節のようなコードを書いてみたが,これだと要素数に極端な不均等が生じるケースがあると気づいたので書き直した。
ちょっと頭を捻ったので記事にしておこうとおもった。