Pythonで配列の要素を並べ替えるのに必要なシャッフルの予想数を見つけるプログラム

要素numsのセットがあるとします。降順ではない順序で並べ替える必要があります。ただし、並べ替えの手法はランダム化されています。配列がソートされているかどうかをチェックします。ソートされていない場合は、ランダムにシャッフルして再度チェックします。すべての要素がソートされるまで、このプロセスを続けます。この場合、それらをソートするために必要なシャッフルの予想数を見つける必要があります。小数点以下6桁までの回答を表示してください。

したがって、入力がnums =[5,2,7]のような場合、3つの順列が可能であるため、出力は6になり、確率は1/3になります

• i =1回の反復でソートされた配列を取得する場合、1/3かかります
• i =2回の反復でソートされた配列を取得する場合、（2/3）*（1/3）が必要になります

i番目の反復回数でソートされた配列を取得する場合、（2/3）^（i-1）*（1/3）

これを解決するには、次の手順に従います-

• numsがソートされている場合、
  • 0を返す
• それ以外の場合、
  • m：=最初は空の新しい辞書
  • numsの各iについて、
    • iがmに存在する場合、
      • m [i]：=m [i] + 1
    • それ以外の場合、
      • m [i]：=1
  • num：=1
  • mの各キーiについて、実行します
    • num：=num * factorial（m [i]）
  • den：=階乗（数値のサイズ）
  • return（den / num）および小数点以下6桁までの四捨五入

例

理解を深めるために、次の実装を見てみましょう-

from math import factorial
def solve(nums):
   if nums == sorted(nums):
      return 0
   else:
      m={}
      for i in nums:
         if i in m:
            m[i]+=1
         else:
            m[i]=1
      num=1
      for i in m:
         num *= factorial(m[i])

      den=factorial(len(nums))
      return round((den/num),6)

nums = [5,2,7]
print(solve(nums))

入力

[5,2,7]

出力

6.0