Python-এ প্রদত্ত শর্তাবলী অনুসরণ করা সমস্ত স্থানচ্যুতিতে উপাদানের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি সেট A আছে যেখানে 1 থেকে n পর্যন্ত সমস্ত উপাদান উপস্থিত রয়েছে। এবং P(A) A-তে উপস্থিত উপাদানগুলির সমস্ত স্থানান্তরকে প্রতিনিধিত্ব করে। আমাদের P(A) তে কতগুলি উপাদান খুঁজে বের করতে হবে যা প্রদত্ত শর্তগুলিকে সন্তুষ্ট করে

পরিসরের সকল i এর জন্য [1, n], A[i] i এর মতো নয়
এখানে k সূচকের একটি সেট আছে {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]। এখন যদি আমরা

এর প্রথম উপাদান বিবেচনা করি

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 এর মান a এর জন্য, করুন
  - যদি a i এর মত হয়, তাহলে
    - লুপ থেকে বেরিয়ে আসুন
- অন্যথায়,
  - করুন
    - বর্তমান :=পি[জে]
    - সাইকেলের_দৈর্ঘ্য :=1
    - যদিও কারেন্ট j এর মত নয়, do
      - কারেন্ট :=p[বর্তমান]
      - সাইকেল_লেংথ :=সাইকেল_লেংথ + 1
    - যদি চক্র_দৈর্ঘ্য 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