Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm số phần tử trong tất cả hoán vị tuân theo các điều kiện nhất định trong Python

Giả sử chúng ta có một tập hợp A mà tất cả các phần tử từ 1 đến n đều có mặt. Và P (A) đại diện cho tất cả các hoán vị của các phần tử có trong A. Chúng ta phải tìm số phần tử trong P (A) thỏa mãn các điều kiện cho trước

  • Đối với tất cả các i trong phạm vi [1, n], A [i] không giống với i
  • Tồn tại tập hợp k chỉ số {i1, i2, ... ik} sao cho A [ij] =ij + 1 với mọi j

Vì vậy, nếu đầu vào là n =3 k =2, thì đầu ra sẽ là 0 vì -

Coi Mảng là 1 được lập chỉ mục. Với N =3 và K =2, chúng ta có thể tìm thấy 2 tập hợp A thỏa mãn tính chất đầu tiên a [i] ≠ i, chúng là [3,1,2] và [2,3,1]. Bây giờ là K =2, chúng ta có thể có 6 phần tử như vậy.

[1,2], [1,3], [2,3], [2,1], [3,1], [3,2]. Bây giờ nếu chúng ta xem xét phần tử đầu tiên của

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

  • [1,2], A [1] ≠ 2
  • [1,3], A [1] =3 nhưng A [3] ≠ 1
  • [2,3], A [2] ≠ 3
  • [2,1], A [2] =1 nhưng A [1] ≠ 2
  • [3,1], A [3] =1 nhưng A [1] ≠ 3
  • [3,2], A [3] ≠ 2

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

  • [1,2], A [1] =2 nhưng A [2] ≠ 1
  • [1,3], A [1] ≠ 3
  • [2,3], A [2] =3 nhưng A [3] ≠ 3
  • [2,1], A [2] ≠ 1
  • [3,1], A [3] =nhưng A [1] ≠ 3
  • [3,2], A [3] ≠ 2

Vì không có phần tử nào của a thỏa mãn các thuộc tính trên, do đó, 0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ps:=tất cả các hoán vị của mảng có các phần tử trong phạm vi [1, n]
  • c:=0
  • đối với mỗi p trong ps, thực hiện
    • đối với mỗi chỉ số i và giá trị a trong p, thực hiện
      • nếu a giống với i, thì
        • ra khỏi vòng lặp
    • nếu không,
      • đối với j trong phạm vi từ 0 đến n - 1, thực hiện
        • hiện tại:=p [j]
        • cycle_length:=1
        • trong khi hiện tại không giống với j, hãy thực hiện
          • hiện tại:=p [hiện tại]
          • cycle_length:=cycle_length + 1
        • nếu cycle_length giống k, thì
          • c:=c + 1
          • ra khỏi vòng lặp
  • trả lại c

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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

Đầu vào 

3, 2

Đầu ra 

0