Problem 524 「初めてのソート その2」

リストをソートする以下のアルゴリズムについて考えよう:

  1. リストの1番目からスタートし, 順番に隣り合った要素のペアをチェックしていく.
  2. もし隣り合った要素が順番通りでなければ:
    a. リストの1番目にそのペアの小さい方の要素を移動する.
    b. ステップ1から作業を再開する.
  3. 全てのペアが順番通りになった時, 停止する.

例えば, リスト { 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! までのインデックス I&sub{n};(P) を割り当てることができる.

この「初めてのソート」でソートするとちょうど k 回のステップが必要な最初の順列の位置を Q(n, k) としよう, すなわち Q(n, k) = min(I&sub{n};(P)) for (F(P) = k). もし F(P) = k となる順列がない場合, Q(n, k) は未定義となる.

n = 4 の場合:

P I&sub{4};(P) F(P)
{1, 2, 3, 4}10Q(4, 0) = 1
{1, 2, 4, 3}24Q(4, 4) = 2
{1, 3, 2, 4}32Q(4, 2) = 3
{1, 3, 4, 2}42
{1, 4, 2, 3}56Q(4, 6) = 5
{1, 4, 3, 2}64
{2, 1, 3, 4}71Q(4, 1) = 7
{2, 1, 4, 3}85Q(4, 5) = 8
{2, 3, 1, 4}91
{2, 3, 4, 1}101
{2, 4, 1, 3}115
{2, 4, 3, 1}123Q(4, 3) = 12
{3, 1, 2, 4}133
{3, 1, 4, 2}143
{3, 2, 1, 4}152
{3, 2, 4, 1}162
{3, 4, 1, 2}173
{3, 4, 2, 1}182
{4, 1, 2, 3}197Q(4, 7) = 19
{4, 1, 3, 2}205
{4, 2, 1, 3}216
{4, 2, 3, 1}224
{4, 3, 1, 2}234
{4, 3, 2, 1}243

任意の k に対し, Q(n, k) が定義できるようなすべての n を検討した場合, 最小となる Q(n, k) を R(k) としよう.

R(12&sup{12};) を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS