在 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=3k=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