![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2022-12-03T15:33:11+00:00","","") *[[Problem 524:https://projecteuler.net/problem=524]] 「初めてのソート その2」 [#e4252aa6] リストをソートする以下のアルゴリズムについて考えよう: + リストの1番目からスタートし, 順番に隣り合った要素のペアをチェックしていく. + もし隣り合った要素が順番通りでなければ:~ a. リストの1番目にそのペアの小さい方の要素を移動する.~ b. ステップ1から作業を再開する. + 全てのペアが順番通りになった時, 停止する. 例えば, リスト { 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''') を割り当てることができる. 整数 {1, 2, ..., '''n'''} のすべての順列 '''P''' を''辞書式順序''で並べ上げ, それぞれの順列に対してリストの位置に対応した 1 から '''n'''! までのインデックス &tex{I_{n}(P)};を割り当てることができる. この「初めてのソート」でソートするとちょうど '''k''' 回のステップが必要な最初の順列の位置を '''Q'''('''n''', '''k''') としよう, すなわち '''Q'''('''n''', '''k''') = min('''I'''&sub{n};('''P''')) for ('''F'''('''P''') = '''k'''). もし '''F'''('''P''') = '''k''' となる順列がない場合, '''Q'''('''n''', '''k''') は未定義となる. この「初めてのソート」でソートするとちょうど '''k''' 回のステップが必要な最初の順列の位置を '''Q'''('''n''', '''k''') としよう, すなわち '''Q'''('''n''', '''k''') = min('''I'''&tex{_{n}};('''P''')) for ('''F'''('''P''') = '''k'''). もし '''F'''('''P''') = '''k''' となる順列がない場合, '''Q'''('''n''', '''k''') は未定義となる. '''n''' = 4 の場合:~ |CENTER:|RIGHT:|RIGHT:|CENTER:|c |'' '''P''' ''|'' '''I'''&sub{4};('''P''') ''|'' '''F'''('''P''') ''|| |'' '''P''' ''|'' '''I'''&tex{_{4}};('''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'''(12&sup{12};) を求めよ. '''R'''(12&tex{^{12}};) を求めよ. // 誤訳？ // Let R(k) = min(Q(n, k)) over all n for which Q(n, k) is defined. // 全てのｎとｋ＝12＾12についてQ(n,k)を検討しその中でQ(n,k)が一番小さくなる数字を答えよ。 IP:112.68.65.182 TIME:"2022-12-04 (日) 00:33:11" REFERER:"http://odz.sakura.ne.jp/projecteuler/" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36"
