सभी क्रमपरिवर्तन में तत्वों की संख्या खोजने का कार्यक्रम जो पायथन में दी गई शर्तों का पालन कर रहे हैं

मान लीजिए कि हमारे पास एक सेट ए है जहां 1 से n तक के सभी तत्व मौजूद हैं। और P(A) A में मौजूद तत्वों के सभी क्रमपरिवर्तन का प्रतिनिधित्व करता है। हमें P(A) में उन तत्वों की संख्या ज्ञात करनी है जो दी गई शर्तों को पूरा करते हैं

सभी i रेंज में [1, n], A[i] i के समान नहीं है
के सूचकांकों का एक सेट मौजूद है {i1, i2, ... ik} जैसे कि A[ij] =ij+1 सभी j

इसलिए, यदि इनपुट n =3 k =2 जैसा है, तो आउटपुट 0 होगा क्योंकि -

विचार करें कि ऐरे 1 अनुक्रमित हैं। N =3 और K =2 के रूप में, हम A के 2 सेट पा सकते हैं जो पहली संपत्ति a[i] i को संतुष्ट करते हैं, वे [3,1,2] और [2,3,1] हैं। अब K =2 के रूप में, हमारे पास ऐसे 6 तत्व हो सकते हैं।

[1,2], [1,3], [2,3], [2,1], [3,1], [3,2]। अब अगर हम

. के पहले तत्व पर विचार करें

पी(ए) -> [3,1,2]

[1,2], ए[1] 2
[1,3], A[1] =3 लेकिन A[3] ≠ 1
[2,3], ए[2] ≠ 3
[2,1], A[2] =1 लेकिन A[1] ≠ 2
[3,1], A[3] =1 लेकिन A[1] ≠ 3
[3,2], ए[3] 2

पी(ए) -> [2,3,1]

[1,2], A[1] =2 लेकिन A[2] ≠ 1
[1,3], ए[1] 3
[2,3], A[2] =3 लेकिन A[3] 3
[2,1], ए[2] ≠ 1
[3,1], A[3] =लेकिन A[1] ≠ 3
[3,2], ए[3] 2

चूँकि a का कोई भी तत्व उपरोक्त गुणों को संतुष्ट नहीं करता है, इसलिए 0.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

ps :=श्रेणी में तत्वों के साथ सरणियों के सभी क्रमपरिवर्तन [1, n]
सी :=0
पीएस में प्रत्येक पी के लिए, करें
- प्रत्येक अनुक्रमणिका i और p में मान a के लिए, करें
  - यदि a, i के समान है, तो
    - लूप से बाहर आएं
- अन्यथा,
  - जे के लिए 0 से n -1 की सीमा में, करो
    - वर्तमान:=p[j]
    - चक्र_लंबाई:=1
    - जबकि करंट j के समान नहीं है, करें
      - वर्तमान:=पी[वर्तमान]
      - चक्र_लंबाई:=चक्र_लंबाई + 1
    - यदि चक्र_लंबाई k के समान है, तो
      - c :=c + 1
      - लूप से बाहर आएं
वापसी सी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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