別の方法もあります。簡単のために長方形の数を100とします。三角数を並べます。
1 3 6 10 15 21 28 36 45 55 66 78 91 105
これとこの逆の並び、
105 91 78 66 55 45 36 28 21 15 10 6 3 1
とでマージ法を使います。先頭の1と105の積は105です。これは100より大きいので、逆並びの方を一つ進めます。91ですね。1と91の積は91で100より小さいので、今度は順並びの方を一つ進めます。
順列 1 1 3 3 3 3 3 3 6 6 10 10 逆列 105 91 78 66 55 45 36 28 28 21 15 10 積 105 91 234 198 165 135 108 84 168 126 150 100
順列と逆列が逆転したらそこで終わりです。
この方法は、上の例だと3が続くところが弱点ですね。
