Problem 524 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 524 へ行く。
  • 1 (2015-11-15 (日) 01:02:03)

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 の場合:

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

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