これは何の記事か

丁合機で順番をミスってしまったので，最初のようにばらしたいときや，ホッチキスで留められていなかったので手で留める必要があったときに，丁合機で最初の状態にしてからもう一回丁合機に入れてあげようとしたときに，この最初の状態にするというアルゴリズムに関するお話です．ググったけどでてこなかった．

以下でソートやばらばらにすると書いてあったら，それは，1枚目や2枚目でそれぞれまとめるということです．つまり，最初の状態にするということです．

似たような事例を調べていたのですが，丁合機でソートというと，どうやら1枚目２枚目……n枚目という風に部数単位にすることのようです．なので，ここでいうソートとは，丁合機におけるソートではないです．

具体的には，1枚目が20枚，2枚目が20枚，3枚目が20枚，4枚目が20枚とすることをここではソートということにします．

方法だけを確認したい人は，例2．10口4枚/部24部の場合をを見てください．

背景

2019年の夏の大学説明会の学生企画で紙を丁合機で束ねていたときに，1部となって出てきた先のホッチキスで留める機構(ステープラ)がぶっ壊れていて留められなかったので困っていました．事務の方を呼んで，待っている間に，もし治ったとして，また手でばらすのは時間が勿体ないなあと思っていたときに，ふと思い付きました．

アルゴリズムの簡単な概要

適当な部数ずつ口に入れて，丁合機を動かします．
このとき，余りが出た場合はよけておいて，別に余りだけを1部ずつ入れて動かします．ばらばらになります．
各枚目が口数と同じ枚数ずつ組になって出てきますよね．その組がいくつか出てくるので，またその組を1部と考えて各口に入れます．

これを繰り返すことでばらばらにできます．余りはそれだけを1組または一部ずつ入れて動かします．ばらばらになります．余りでばらばらにしたものと，余りにならなかったものでばらばらにしたものを合わせてあれば終わりです．

具体例は例2．10口4枚/部24部の場合をみてください．

アルゴリズム本体

まず，仮定として，この丁合機は $\displaystyle k$ 口あるとします．また，1部当たり $\displaystyle j$ 枚， $\displaystyle N$ 部であるとします．つまり，1部が最大で $\displaystyle k$ 枚あるということです．結果を先に示しておくと，このアルゴリズムを用いると最大

\begin{aligned} O(N) = 2 \lfloor \log_k N \rfloor +1 \end{aligned}

回人の手でばらすこととなります．ちなみにこのオーダーは丁合機に入れる回数です．

もし人間がばらす場合は $\displaystyle O(N)=jN$ ですね．

さて，このアルゴリズムを考えていきましょう．

例示は理解の試金石ということで，まずは簡単な場合の例から考えて次に一般化していきましょう．読みにくい文章で分かりにくくなっていると思うので，紙にペンで書いてみるか，小さな紙にページ番号とか振って実際にやってみると良いかと思います．読みにくい文章でごめんなさい．

例1．10口 4枚/部 10部の場合

いま， $\displaystyle k=10,n=40$ ですね．

これはすでに1枚目から4枚目までが順番に並んでいてこれを1部として10部あるということですね．では，これを1部ずつ口に入れます．するとどうでしょうか．出てきた紙は，1枚目が10枚，2枚目が10枚，3枚目が10枚，4枚目が10枚という順番に出てきますね．ちゃんとばらばらになりました．人間のかかった手数は1(丁合機にセットする回数)です．

例2．10口 4枚/部 24部の場合

いま， $\displaystyle k=10,n=96$ ですね．

じゃあこれを適当に口につっこみます．ここでは，それぞれの口に[3,3,3,3,2,2,2,2,2,2]部ずつ入れたとしましょう．

すると，すると最初の2部ずつの分，すなわち，80枚は，1枚目10枚，2枚目10枚，3枚目10枚，4枚目10枚，1枚目10枚，2枚目10枚，3枚目10枚，4枚目10枚となって重なっていますね．

で，最初の3,3,3,3だった部分は1,1,1,1となり，1部ずつが例1と同様に1枚目4枚，2枚目4枚，3枚目4枚，4枚目4枚となってでてくるので分けておきましょう．(A)

次に，80枚について考えましょう．

この80枚は40枚ずつに分けて口につっこみましょう．

すると，1枚目20枚，...,4枚目20枚とでてきます．(B)

これもばらして(A)，(B)を重ねてあげるとばらけてますね．

これだと人間の手数は3回ですね．

アルゴリズムの一般化

丁合機の口数 $\displaystyle k$ ，紙の枚数 $\displaystyle n枚$ ， $\displaystyle j$ を1部あたりの枚数として(枚/部)， $\displaystyle \frac{n}{j}$ 部( $\displaystyle =N$ )．ただし， $\displaystyle j \leq k$ ．

$\displaystyle N$ 部を $\displaystyle N \div k$ の商( $\displaystyle =Q$ )の部数ずつ口に入れます．(AA)
余った分( $\displaystyle N \div k$ の剰余)は1回入れるだけでソート可能ですね．
(AA)を丁合機で実行した場合，1枚目が $\displaystyle k$ 枚の，2枚目が $\displaystyle k$ 枚， $\displaystyle j$ 枚目が $\displaystyle k$ 枚と出てきます．これら $\displaystyle jk$ 枚を1組と呼ぶことにします．
するといま， $\displaystyle Q$ 組みあるという事が分かります．
この1組を1部として考えて，1に戻ります．つまり $\displaystyle N=Q$ ですね．

以上を繰り替えすことによってソートされていきます．

オーダーを考える

上記のアルゴリズムで余りが出る場合，すなわり，2が実行されるかどうかであるが，これの回数は高々余りが全てなかった場合に突っ込んだ回数と同じであるから，この余りが出なかった場合の回数を考えて2倍すればよい．

なので，余りが出ない場合を考える．

1回突っ込むと， $\displaystyle k$ 枚ずつ $\displaystyle i(=1,2,\dots, j)$ 枚目が揃う．

これを1組として，突っむと $\displaystyle k^{2}$ 枚ずつ揃う． $\displaystyle N$ 回繰り返すと $\displaystyle k^{N}$ 枚揃う．

$\displaystyle N \leq k^{m}$ となるような自然数 $\displaystyle m$ をみつけてやればよくて，

\begin{aligned} m &=& \lceil \log_k N \rceil \\ &=& \lfloor \log_k N \rfloor +1 \end{aligned}

となる．

面倒だけど10口288部の図を用意しました．

f:id:OShun:20200218182548p:plain — 10口288部の場合

青い矢印が人間が手を動かすところです．この木の最も長いエッジ(ここでは，最も矢印の本数が多いもの)は3ですね．これは $\displaystyle \lfloor \log_k N \rfloor +1$ に等しいです．最後のノードへ延びる矢印以外は余りが発生する可能性があるので2倍すれば良いから，

\begin{aligned} O(N)=2\lfloor \log_k N \rfloor +1 \end{aligned}

と対数オーダーになりました．

ちなみに，丁合機を動かしているのは根以外のノード数です．つまりは5回．まあ，人間が手で入れてやるのと同じ回数なのは当然ですね．

例3．10口 4枚/部 188部

いま， $\displaystyle k=10,n=732$ ですね．

口に18部( $\displaystyle =Q$ )ずつ入れて8部余る．この18部を実行すると18組できますね．これを10組と8組に分けて，それぞれ実行してソートされました．最初の8部も実行して完全にすべてばらばらになりました．突っ込んだ回数は4回ですね． $\displaystyle 2 \lfloor \log_{10} 188 \rfloor +1 =5$

いやいや，手で分けるとかいう面倒なことしてるやん

確かにそうですが，丁合機から出てくるものは部単位になっているので，めんどうなことではないと思います．それでも分けるという時間を考えるとちょっと時間がかかりますね．

いやいや，それでも口に入れるときに同じ部数ずつ分けないといけないんじゃ？

そんなことないです．もしどこかが空になったら止まります．適当な部数で入れておいて(部数単位で入れることが簡単なのは，部単位で出てくることから分かりますよね)，止まったら，多いところから少ないところに移してあげましょう．これぐらいの手間，人間の手で全部ばらすことに比べてら圧倒的に楽ですね．

余談

k=1

$\displaystyle O(n)=log_1 n$

まあ，底が1なので計算できないのであるが，丁合機で実行しているとすると，いつまで経ってもソートが終わらない．順番が逆になるぐらいだ．

ステープラ

ちなみに，背景で述べたステープラですが，直らなかったので，数百部を手でホッチキスで留めました．

これで全世界の事務員さんとかが救われる？

そんなことないかな......

最後に

最後までよんでくださりありがとうございました．

一見， $\displaystyle k=1$ というのは何も変えていないように見えて，順番を逆にしていたりします．

$\displaystyle k=1$ を2回すると元に戻ります．

数学的に大変面白い構造になっているような気がしていて，それは何だろうかとたまに考えていました．

結局１年ほど経ったのですがよく分かりませんでした．

初めはあみだくじと似ているので巡回群となっているのではないかなと思いました．しかし，いくつかのまとまった塊で操作をしているため，うまい具合にそもそも群の構造に当てはめることができませんでした......

オーダーを対数にしていますが，本当はそれぞれで入れるときに分けるという作業をしているので実際には線形になるんじゃないかなとか思ったりしています．

何か間違っていたり，関連したものがあったりしたら教えていただきたいです．

よろしくお願いいたします．

Live and let live.

丁合機を用いて対数オーダーで紙を元通りにするアルゴリズム