শুধুমাত্র পাইথনে প্রদত্ত সূচকগুলির মধ্যে অদলবদল ব্যবহার করে অ্যারে সাজানো যায় কিনা তা পরীক্ষা করুন

ধরুন আমাদের একটি অ্যারে আছে যাকে nums বলা হয় রেঞ্জ [0, n – 1] থেকে অনন্য মান সহ। এই অ্যারে সাজানো হয় না. আমাদের জোড়ার আরেকটি অ্যারে রয়েছে যেখানে প্রতিটি জোড়া সূচক রয়েছে যেখানে অ্যারের উপাদানগুলি অদলবদল করা যেতে পারে। আমরা একাধিকবার অদলবদল করতে পারি। আমরা এই অদলবদল ব্যবহার করে সাজানো ক্রমে অ্যারে সাজাতে পারি কিনা তা আমাদের পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুট সংখ্যার মত হয় =[6,1,7,3,0,5,4,2] জোড়া =[(0,4),(6,0),(2,7)], তাহলে আউটপুট True হবে, যেমন আমরা সূচী অদলবদল করতে পারি (2,7) অ্যারে হবে [6,1,2,3,0,5,4,7], তারপর swap (6,0), অ্যারে হবে [4, 1,2,3,0,5,6,7], তারপর [0,1,2,3,4,5,6,7] পেতে (0,4) অদলবদল করুন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

N :=সংখ্যার আকার, P :=জোড়া অ্যারেতে জোড়ার সংখ্যা
v :=সাবলিস্টের N সংখ্যা সহ একটি তালিকা
পরিদর্শন করেছেন :=একটি নতুন সেট
আমি 0 থেকে P রেঞ্জের জন্য, কর
- পেয়ারের দ্বিতীয় সূচী[i] সন্নিবেশ করান v[পেয়ারের প্রথম সূচক[i]]
- পেয়ারের প্রথম সূচী [i] সন্নিবেশ করান v[পেয়ারের দ্বিতীয় সূচক[i]]
আমি 0 থেকে N রেঞ্জের জন্য, কর
- যদি আমি পরিদর্শন না করি, তাহলে
  - que :=একটি ডবল শেষ সারি
  - arr_first :=একটি নতুন তালিকা
  - arr_second :=একটি নতুন তালিকা
  - আমি ভিজিট করেছি হিসেবে চিহ্নিত করুন
  - que এর শেষে i ঢোকান
  - যখন que খালি না, do
    - u :=que এর ফ্রন্ট এলিমেন্ট এবং que এর ফ্রন্ট এলিমেন্ট ডিলিট করুন
    - arr_first এর শেষে u ঢোকান
    - arr_second এর শেষে nums[u] ঢোকান
    - v[u]-এ প্রতিটি s-এর জন্য, করুন
      - যদি s পরিদর্শন না করা হয়, তাহলে
        
        গুলিকে পরিদর্শন করা হিসাবে চিহ্নিত করুন
        
        que এর শেষে s ঢোকান
  - arr_first :=তালিকা সাজান arr_first
  - arr_second :=তালিকা সাজান arr_second
  - যদি arr_first arr_second এর মত না হয়, তাহলে
    - মিথ্যে ফেরত দিন
সত্য ফেরান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ কোড

from collections import deque

def solve(nums, pairs):
   N = len(nums)
   P = len(pairs)
   v = [[] for i in range(N)]
   visited = set()
 
   for i in range(P):
      v[pairs[i][0]].append(pairs[i][1])
      v[pairs[i][1]].append(pairs[i][0])
 
   for i in range(N):
      if i not in visited:
         que = deque()
         arr_first = []
         arr_second = []
 
         visited.add(i)
         que.append(i)
 
         while len(que) > 0:
           u = que.popleft()
           arr_first.append(u)
           arr_second.append(nums[u])
 
           for s in v[u]:
               if s not in visited:
                 visited.add(s)
                 que.append(s)
 
         arr_first = sorted(arr_first)
         arr_second = sorted(arr_second)
         
         if arr_first != arr_second:
           return False
   return True
 
nums = [6,1,7,3,0,5,4,2]
pairs = [(0,4),(6,0),(2,7)]
print(solve(nums, pairs))

ইনপুট

[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]

আউটপুট

True