*[[Problem 367:http://projecteuler.net/problem=367]] 「ボゾソート」 [#z998e3d9]
''ボゴソート'' (bogo sort) より若干効率的な別種のソート, ''ボゾソート'' (bozo sort) は, 入力数列がソートされているかをチェックし, ソートされていなければランダムに二つの要素を入れ替える. この操作を数列がソートされるまで繰り返す.
入力数列を最初の4つの自然数からなるすべての順列として, 入れ替えの回数の期待値を計算すると, 4! 個の入力数列に対する入れ替え回数の平均は 24.75 となる. ~
すでに数列がソートされている場合は入れ替え回数を0回とみなす.
この問題では, ボゾソートの変種について考える. ~
数列がソートされていなければランダムに3個の要素を選び, その3個の要素をランダムにシャッフルして入れ替える. ~
これら3個の要素の置換は 3!=6, つまり6通りあり, 等しく起こりうるとする. ~
すでに数列がソートされている場合はシャッフル回数を0回とみなすことにしよう. ~
入力数列を最初の4つの自然数からなるすべての順列として, シャッフルの回数の期待値を計算すると, 4! 個の入力数列に対するシャッフル回数の平均は 27.5 となる. ~
ここで入力数列を最初の11個の自然数からなるすべての順列として考えよう. ~
11! 個の入力数列に対するシャッフル回数の平均, すなわちこのソートアルゴリズムが行われた場合のシャッフル回数の期待値はいくらになるだろう?
回答は整数になるよう四捨五入して答えよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
