用 Python 编写程序，用于查找对数组元素进行排序所需的预期洗牌次数

pythonserver side programmingprogramming更新于 2026/2/1 11:56:17

假设我们有一组元素 nums。我们必须按非递减顺序对它们进行排序。但排序技术是随机的。我们将检查数组是否已排序，如果没有，则随机洗牌并再次检查。继续此过程，直到所有元素都已排序。在这种情况下，我们必须找到对它们进行排序所需的预期洗牌次数。显示精确到小数点后 6 位的答案。

因此，如果输入为 nums = [5,2,7]，则输出将为 6，因为有 3 种可能的排列，因此概率为 1/3

如果我们在 i = 1 次迭代时获得排序数组，则需要 1/3
如果我们在 i = 2 次迭代时获得排序数组，则需要 (2/3)*(1/3)

如果我们在第 i 次迭代时获得排序数组，则需要 (2/3)^(i-1) * (1/3)

要解决这个问题，我们将遵循以下步骤 −

如果 nums 已排序，则
- 返回0
否则，
- m:= 一个新的字典，最初为空
- 对于 nums 中的每个 i，执行
  - 如果 i 存在于 m 中，则
    - m[i] := m[i] + 1
  - 否则，
    - m[i]:= 1
- num:= 1
- 对于 m 中的每个键 i，执行
  - num := num * factorial(m[i])
- den:= factorial(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))