用 Python 编写程序，查找所有排列中符合给定条件的元素数量

pythonserver side programmingprogramming更新于 2026/2/1 7:40:17

假设我们有一个集合 A，其中存在从 1 到 n 的所有元素。P(A) 表示 A 中存在的所有元素排列。我们必须找到 P(A) 中满足给定条件的元素数量

对于范围 [1, n] 中的所有 i，A[i] 与 i 不同
存在一组 k 索引 {i1, i2, ... ik}，使得对于所有 j < k 且 A[ik] = i1(循环)，A[ij] = ij+1。

因此，如果输入为 n = 3 k = 2，则输出将为 0，因为 -

考虑数组的索引为 1。当 N = 3 且 K = 2 时，我们可以找到 2 个满足第一个属性 a[i] ≠ i 的 A 集合，它们是 [3,1,2] 和 [2,3,1]。现在当 K = 2 时，我们可以有 6 个这样的元素。

[1,2], [1,3],[2,3], [2,1], [3,1], [3,2]。现在如果我们考虑的第一个元素

P(A) -> [3,1,2]

[1,2], A[1] ≠ 2
[1,3], A[1] = 3 but A[3] ≠ 1
[2,3], A[2] ≠ 3
[2,1], A[2] = 1 but A[1] ≠ 2
[3,1], A[3] = 1 but A[1] ≠ 3
[3,2], A[3] ≠ 2

P(A) -> [2,3,1]

[1,2], A[1] = 2 but A[2] ≠ 1
[1,3], A[1] ≠ 3
[2,3], A[2] = 3 but A[3] ≠ 3
[2,1], A[2] ≠ 1
[3,1], A[3] = but A[1] ≠ 3
[3,2], A[3] ≠ 2

由于 a 中的任何元素都不满足上述属性，因此为 0。

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

ps := 元素范围为 [1, n] 的数组的所有排列
c := 0
对于 ps 中的每个 p，执行
- 对于 p 中的每个索引 i 和值 a，执行
  - 如果 a 与 i 相同，则
    - 退出循环
- 否则，
  - 对于范围在 0 到 n - 1 内的 j，执行
    - current := p[j]
    - cycle_length := 1
    - 当 current 与 j 不同时，执行
      - current := p[current]
      - cycle_length := cycle_length + 1
    - 如果 cycle_length 与 k 相同，则
      - c := c + 1
      - 退出循环
返回 c

示例

让我们看看下面的实现以便更好地理解 −

import itertools

def solve(n, k):
   ps = itertools.permutations(range(n), n)
   c = 0
   for p in ps:
      for i, a in enumerate(p):
         if a == i:
            break
      else:
         for j in range(n):
            current = p[j]
            cycle_length = 1
            while current != j:
               current = p[current]
               cycle_length += 1
            if cycle_length == k:
               c += 1
               break
   return c

n = 3
k = 2
print(solve(n, k))