পাইথনে প্রদত্ত শর্তাবলী মেনে চলা পারমুটেশন উপাদান সংখ্যা বের করার প্রোগ্রাম

ধরুন, একটি সেট A আছে যেখানে ১ থেকে n পর্যন্ত সকল উপাদান উপস্থিত। P(A) উপস্থিত করে A-র উপাদানগুলোর সকল পারমুটেশন (permutation)। আমাদের P(A)-র সতট उपাদান সংখ্যা বের করতে হবে যা নিচের শর্তাবলী পূরণ করে:

সকল i রেঞ্জ [1, n]-এর জন্য, A[i] এবং i একই নয়
k সংখ্যক ইন্ডেক্সের একটি সেট {i1, i2, ... ik} আছে যাতে A[ij] = ij+1 সকল j < k এর জন্য এবং A[ik] = i1 (সাইক্লিক)।

সুতরাং, যদি ইনপুট হয় n = 3, k = 2, তবে আউটপুট হবে 0 কারণ -

অ্যারের ১-ইন্ডেক্সড (1-indexed) মনে করুন। যেহেতু N = 3 এবং K = 2, আমরা A-র ২টি সেট পাই যা প্রথম প্রোপার্টি পূরণ করে a[i] ≠ i, সেগুলো হল [3,1,2] এবং [2,3,1]। এখন K = 2 হলে, আমরা ৬টি takie উপাদান পেতে পারি:

[1,2], [1,3], [2,3], [2,1], [3,1], [3,2]। এখন যদি আমরা P(A)-র প্রথম উপাদান বিবেচনা করি:

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] = 1 কিন্তু A[1] ≠ 3
[3,2], A[3] ≠ 2

যেহেতু a-র কোণো উপাদান উপরের প্রোপার্টিগুলো পূরণ করে না, অতএব ফলাফল 0।

এটি সমাধান করার জন্য, আমরা নিচের ধাপগুলো অনুসরণ করব:

ps := [1, n] রেঞ্জের উপাদান ধারণকারী অ্যারের সকল পারমুটেশন
c := 0
প্রতিটি p in ps এর জন্য, করুন:
- প্রতিটি ইন্ডেক্স i এবং মান a in p এর জন্য, করুন:
  - যদি a এবং i একই হয়, তবে:
    - লুপ থেকে বের হয়ে যান
- অন্যথায়:
  - j in range 0 to 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