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

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

• 对于 [1, n] 范围内的所有 i，A[i] 与 i 不同

• 存在一组 k 个索引 {i1, i2, ... ik} 使得 A[ij] = ij+1 对于所有 j < k 和 A[ik] = i1（循环）。

因此，如果输入类似于 n = 3 k = 2，那么输出将为 0，因为 -

考虑数组的索引为 1。由于 N = 3 和 K = 2，我们可以找到满足第一个属性 a[i] ≠ i 的 2 组 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 但 A[3] ≠ 1

• [2,3], A[2] ≠ 3

• [2,1], A[2] = 1 但 A[1] ≠ 2

• [3,1], A[3] = 1 但 A[1] ≠ 3

• [3,2], A[3] ≠ 2

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

• [1,2], A[1] = 2 但 A[2] ≠ 1

• [1,3], A[1] ≠ 3

• [2,3], A[2] = 3 但 A[3] ≠ 3

• [2,1], A[2] ≠ 1

• [3,1], A[3] = 但 A[1] ≠ 3

• [3,2], A[3] ≠ 2

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

示例

让我们看看以下实现以获得更好的理解 -

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

输入

3, 2

0