Chương trình tính số lần xáo trộn kỳ vọng để sắp xếp mảng trong Python

Cho mảng nums. Lặp: nếu chưa sắp xếp thì random shuffle. Tìm kỳ vọng số lần shuffle đến khi sắp xếp. Đáp án làm tròn 6 chữ số.

Thuật toán

• Nếu đã sắp xếp → 0.
• Số hoán vị khác nhau = n! / ∏(freq[i]!).
• Xác suất sắp xếp đúng mỗi lần = 1 / (số hoán vị).
• Kỳ vọng phân bố幂几何 = số hoán vị.

Ví dụ

from math import factorial

def solve(nums):
    if nums == sorted(nums):
        return 0
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    denom = 1
    for v in freq.values():
        denom *= factorial(v)
    total_perm = factorial(len(nums)) // denom
    return round(total_perm, 6)

print(solve([5, 2, 7]))  # Output: 6.0

Giải thích

[5,2,7] có 3! = 6 hoán vị → kỳ vọng = 6.