กำหนดชุดข้อมูล nums เรียงแบบ non-decreasing ด้วยวิธีสุ่ม: ตรวจสอบว่าเรียงแล้วหรือยัง ถ้ายัง ให้ random shuffle แล้วตรวจสอบใหม่ ทำซ้ำจนเรียง หาจำนวนการ shuffle คาดการณ์ แสดง 6 ตำแหน่งทศนิยม
เช่น nums = [5,2,7] ผลลัพธ์คือ 6 เพราะมี 3 permutations ความน่าจะเป็น 1/3
วิธีแก้ปัญหา
- ถ้า nums เรียงแล้ว: คืนค่า 0
- มิฉะนั้น
- m := dictionary ว่าง
- นับความถี่แต่ละค่าใน nums
- num := 1
- สำหรับแต่ละ key i ใน m: num := num * factorial(m[i])
- den := factorial(len(nums))
- คืนค่า (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))Input
[5,2,7]
Output
6.0
