前回の最後にちょっと書いた、配列を直接並び替える方法です。
１～５の並びを考える時、5桁の数とみなして考えます。
この5桁で、一番小さな数になる並びは、12345です。
ここからスタートして、次に大きな数をひたすら探していって、
もっとも大きな数になる、54321になるまで順にたどっていけばいいわけです。
どうやって、次に大きな数を探すかですが、
まず考えないといけないのは、
なるべく下の位だけを取り替えて上の位は触らない、ってことです。
では、12345の次の数を探しましょう。
まず、一番下の位の5を一時領域に置きます。
次の位は4が入っているので、5に置き換えます。
そして、5が入っていた所に4を置いて、12354が次に大きい数です。
12354の次も見てみましょう。
先ほどと同じように4を一時領域に置きます。
次の位は5ですが、4と交換してしまうと求める数が小さくなるので、
これもまた一時領域に置きます。
次は3で4か5と交換できますが、3より大きくて一番小さい4と交換します。
最後に空白に3と5を並べるわけですが、35と53だと35の方が小さいので
35を置いて、12435が次に大きい数になります。
まとめると、
・一時領域に自分より大きい数がなければ、一時領域に移動。
・一時領域に自分より大きい数があれば、その数と交換。
候補が複数あれば、候補の中で一番小さい数にする。
・交換が出来たら、空白に一時領域の数を小さい順に並べる。
なお、この方法だと、1122という風に、同じ数が複数あってもいけます。
自分より大きい数を探してくるので、重複するパターンを2度数えることもありません。
#手書きメソッド結構お気に入り…汚い字だから読みにくいかな？