파이썬에서 주어진 조건을 따르는 모든 순열의 요소 수를 찾는 프로그램

<시간/>

1에서 n까지의 모든 요소가 존재하는 집합 A가 있다고 가정합니다. 그리고 P(A)는 A에 존재하는 모든 원소의 순열을 나타냅니다. 우리는 주어진 조건을 만족하는 P(A)에서 원소의 수를 찾아야 합니다.

[1, n] 범위의 모든 i에 대해 A[i]는 i와 동일하지 않습니다.
모든 j

따라서 입력이 n =3 k =2와 같으면 출력은 -

이기 때문에 0이 됩니다.

Array의 인덱스가 1이라고 가정합니다. N =3 및 K =2이므로 첫 번째 속성 a[i] ≠ i를 충족하는 A의 2개 집합을 찾을 수 있습니다. 이들은 [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

의 어떤 요소도 위의 속성을 만족하지 않으므로 0입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ps :=[1, n] 범위의 요소가 있는 배열의 모든 순열
c :=0
ps의 각 p에 대해 수행
- 각 인덱스 i와 p의 값에 대해 다음을 수행합니다.
  - i와 같으면
    - 루프에서 나오다
- 그렇지 않으면
  - 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
    - 현재 :=p[j]
    - 주기 길이 :=1
    - 현재가 j와 같지 않은 동안 do
      - 현재 :=p[현재]
      - 주기_길이 :=주기_길이 + 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