n個の物を順番に並べる時、並べ方は何通りあるか。
これは、n!で表せます。
これに番号をつけて管理する時、
ちょっと変わった進数表現をしてやればいいです。
1桁目は0,1だけ(2で繰り上がる)
2桁目は0,1,2だけ(3で繰り上がる)
3桁目は0,1,2,3だけ(4で繰り上がる)
4桁目は0,1,2,3,4だけ(5で繰り上がる)
こんな感じですね
0, 1, 10, 11, 20, 21, 100,
101, 110, 111, 120, 121, 200,
... , 300, 301, 310, 311, 320, 321, 1000
ちょっと不思議な感じですね
では、これを数字の列に直すとき、どうするか。
それぞれの桁数は挿入位置を表しています。
n桁目はn+1の数字の挿入位置です。
例として｢310｣ってのを4つの数字のならびに直してみましょう。
1桁目は0なので、2の挿入位置は0
2桁目は1なので、3の挿入位置は1
3桁目は3なので、4の挿入位置は3
ということで、2314という並びになるんですね。
ただ、この方法はすべての順列を作って何かをする、というのには向きません。
そういう場合は、直接配列を並び替えてやった方が速いです。