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