Chương trình tìm số lần xáo trộn dự kiến ​​được yêu cầu để sắp xếp các phần tử của một mảng trong Python

Giả sử chúng ta có một tập hợp các phần tử nums. Chúng ta phải sắp xếp chúng theo trình tự không giảm dần. Nhưng kỹ thuật sắp xếp là ngẫu nhiên. Chúng tôi sẽ kiểm tra xem mảng có được sắp xếp hay không, nếu không thì xáo trộn ngẫu nhiên nó và kiểm tra lại. Cho đến khi tất cả các phần tử được sắp xếp tiếp tục quá trình này. Trong trường hợp này, chúng ta phải tìm số lần xáo trộn dự kiến ​​cần thiết để sắp xếp chúng. Hiển thị câu trả lời lên đến 6 chữ số thập phân.

Vì vậy, nếu đầu vào là nums =[5,2,7], thì đầu ra sẽ là 6 vì có thể có 3 hoán vị, do đó xác suất là 1/3

• Nếu chúng ta nhận được mảng đã sắp xếp ở i =1 số lần lặp, thì nó sẽ mất 1/3
• Nếu chúng ta nhận được mảng đã sắp xếp ở i =2 số lần lặp, thì nó sẽ mất (2/3) * (1/3)

Nếu chúng ta nhận được mảng được sắp xếp ở số lần lặp thứ i, thì nó sẽ mất (2/3) ^ (i-1) * (1/3)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu nums được sắp xếp, thì
  • trả về 0
• nếu không,
  • m:=một từ điển mới ban đầu trống
  • đối với mỗi tôi trong nums, hãy thực hiện
    • nếu tôi có mặt trong m, thì
      • m [i]:=m [i] + 1
    • nếu không,
      • m [i]:=1
  • num:=1
  • đối với mỗi khóa i trong m, hãy thực hiện
    • num:=num * giai thừa (m [i])
  • den:=giai thừa (kích thước của nums)
  • return (den / num) và làm tròn đến 6 chữ số thập phân

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[5,2,7]

Đầu ra

6.0