जांचें कि क्या सरणी को केवल पायथन में दिए गए सूचकांकों के बीच स्वैप का उपयोग करके क्रमबद्ध किया जा सकता है

मान लीजिए कि हमारे पास रेंज [0, n - 1] से अद्वितीय मानों के साथ nums नामक एक सरणी है। यह सरणी क्रमबद्ध नहीं है। हमारे पास जोड़े की एक और सरणी भी है जहां प्रत्येक जोड़ी में सूचकांक होते हैं जहां सरणी के तत्वों को स्वैप किया जा सकता है। हम कई बार स्वैप कर सकते हैं। हमें यह जांचना होगा कि क्या हम इन स्वैप का उपयोग करके सरणी को क्रमबद्ध क्रम में व्यवस्थित कर सकते हैं या नहीं।

इसलिए, यदि इनपुट अंकों की तरह है =[6,1,7,3,0,5,4,2] जोड़े =[(0,4), (6,0), (2,7)], तो आउटपुट ट्रू होगा, जैसा कि हम स्वैप कर सकते हैं इंडेक्स (2,7) ऐरे [6,1,2,3,0,5,4,7] होंगे, फिर स्वैप (6,0), ऐरे [4, 1,2,3,0,5,6,7], फिर [0,1,2,3,4,5,6,7] पाने के लिए (0,4) स्वैप करें।

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

• N :=अंकों का आकार, P :=जोड़े सरणी में युग्मों की संख्या
• v :=एक सूची जिसमें एन संख्या में सबलिस्ट हैं
• विज़िट किया :=एक नया सेट
• मैं के लिए 0 से पी की सीमा में, करते हैं
  • जोड़ियों की दूसरी अनुक्रमणिका डालें[i] v में [जोड़े की पहली अनुक्रमणिका[i]]
  • जोड़ों की पहली अनुक्रमणिका डालें[i] v[जोड़ियों की दूसरी अनुक्रमणिका[i]]
  . में डालें
• मैं के लिए 0 से N की सीमा में, करते हैं
  • अगर मैं नहीं जाता, तो
    • que :=एक डबल एंडेड कतार
    • arr_first :=एक नई सूची
    • arr_second :=एक नई सूची
    • देखे गए के रूप में चिह्नित करें
    • क्यू के अंत में i डालें
    • जबकि क्यू खाली नहीं है, करें
      • u :=que का फ्रंट एलिमेंट और que का फ्रंट एलिमेंट डिलीट करें
      • arr_first के अंत में आपको सम्मिलित करें
      • arr_second के अंत में nums[u] डालें
      • v[u] में प्रत्येक s के लिए, do
        • यदि s का दौरा नहीं किया जाता है, तो
          • देखे गए के रूप में चिह्नित करें
          • क्यू के अंत में 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