リストをソートする以下のアルゴリズムについて考えよう:
例えば, リスト { 4 1 3 2 } は以下のようにしてソートされる:
4 1 3 2 (4 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 4 3 2 (4 と 3 が順番どおりでないのでリストの1番目に 3 を移動する)
3 1 4 2 (3 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 3 4 2 (4 と 2 が順番どおりでないのでリストの1番目に 2 を移動する)
2 1 3 4 (2 と 1 が順番どおりでないのでリストの1番目に 1 を移動する)
1 2 3 4 (これでリストはソートされた)
リスト L をソートする際に実行されるステップ 2a の回数を F(L) としよう. 例えば, F({ 4 1 3 2}) = 5 となる.
整数 {1, 2, ..., n} のすべての順列 P を辞書式順序で並べ上げ, それぞれの順列に対してリストの位置に対応した 1 から n! までのインデックス In(P)を割り当てることができる.
この「初めてのソート」でソートするとちょうど k 回のステップが必要な最初の順列の位置を Q(n, k) としよう, すなわち Q(n, k) = min(In(P)) for (F(P) = k). もし F(P) = k となる順列がない場合, Q(n, k) は未定義となる.
n = 4 の場合:
P | I4(P) | F(P) | |
{1, 2, 3, 4} | 1 | 0 | Q(4, 0) = 1 |
{1, 2, 4, 3} | 2 | 4 | Q(4, 4) = 2 |
{1, 3, 2, 4} | 3 | 2 | Q(4, 2) = 3 |
{1, 3, 4, 2} | 4 | 2 | |
{1, 4, 2, 3} | 5 | 6 | Q(4, 6) = 5 |
{1, 4, 3, 2} | 6 | 4 | |
{2, 1, 3, 4} | 7 | 1 | Q(4, 1) = 7 |
{2, 1, 4, 3} | 8 | 5 | Q(4, 5) = 8 |
{2, 3, 1, 4} | 9 | 1 | |
{2, 3, 4, 1} | 10 | 1 | |
{2, 4, 1, 3} | 11 | 5 | |
{2, 4, 3, 1} | 12 | 3 | Q(4, 3) = 12 |
{3, 1, 2, 4} | 13 | 3 | |
{3, 1, 4, 2} | 14 | 3 | |
{3, 2, 1, 4} | 15 | 2 | |
{3, 2, 4, 1} | 16 | 2 | |
{3, 4, 1, 2} | 17 | 3 | |
{3, 4, 2, 1} | 18 | 2 | |
{4, 1, 2, 3} | 19 | 7 | Q(4, 7) = 19 |
{4, 1, 3, 2} | 20 | 5 | |
{4, 2, 1, 3} | 21 | 6 | |
{4, 2, 3, 1} | 22 | 4 | |
{4, 3, 1, 2} | 23 | 4 | |
{4, 3, 2, 1} | 24 | 3 |
任意の k に対し, Q(n, k) が定義できるようなすべての n を検討した場合, 最小となる Q(n, k) を R(k) としよう.
R(1212) を求めよ.