Python에서 배열의 요소를 정렬하는 데 필요한 셔플 예상 수를 찾는 프로그램

요소 집합이 있다고 가정합니다. 내림차순으로 정렬해야 합니다. 그러나 정렬 기술은 무작위입니다. 배열이 정렬되었는지 여부를 확인하고 그렇지 않은 경우 무작위로 섞고 다시 확인합니다. 모든 요소가 정렬될 때까지 이 프로세스를 계속합니다. 이 경우 우리는 그것들을 정렬하는 데 필요한 셔플의 예상 수를 찾아야 합니다. 답은 소수점 이하 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)

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 숫자가 정렬되면
  • 0을 반환
• 그렇지 않으면,
  • m:=처음에는 비어 있는 새 사전
  • 숫자 단위의 각 i에 대해 다음을 수행합니다.
    • i가 m에 있으면
      • m[i] :=m[i] + 1
    • 그렇지 않으면
      • m[i]:=1
  • 숫자:=1
  • m의 각 키 i에 대해 다음을 수행합니다.
    • num :=num * 계승(m[i])
  • den:=계승(숫자의 크기)
  • 반환(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