Python程序：查找满足给定条件的所有排列中的元素个数

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

  • 对于所有i∈[1, n]，A[i]不等于i。
  • 存在一个k个索引的集合{i1, i2, ... ik}，使得对于所有j < k，A[ij] = ij+1，并且A[ik] = i1（循环）。

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

考虑数组从1开始索引。由于N = 3且K = 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 但 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] ≠ 2
  • [2,1]，A[2] ≠ 1
  • [3,1]，A[3] = 1 但 A[1] ≠ 3
  • [3,2]，A[3] ≠ 2

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

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

  • ps := 元素范围在[1, n]内的所有数组排列
  • c := 0
  • 对于ps中的每个p，执行：
    • 对于p中的每个索引i和值a，执行：
      • 如果a等于i，则
        • 退出循环
    • 否则，
      • 对于j从0到n-1，执行：
        • 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))

输入

3, 2

输出

0

更新于：2021年10月25日

225 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告