Python में दी गई शर्तों का पालन करने वाले सभी क्रमचय में एलिमेंट्स की संख्या खोजने का प्रोग्राम

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

रेंज [1, n] में सभी i के लिए, 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 के 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]। अब यदि हम मानते हैं तो

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।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

ps := रेंज [1, n] में एलिमेंट्स वाले ऐरे के सभी क्रमचय
c := 0
ps में प्रत्येक p के लिए, करें
- p में प्रत्येक इंडेक्स i और मान a के लिए, करें
  - यदि a, i के समान है, तो
    - लूप से बाहर आएं
- अन्यथा,
  - j के लिए range 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