Kiểm tra xem mảng có thể được sắp xếp bằng cách sử dụng hoán đổi giữa các chỉ số đã cho chỉ trong Python hay không

Giả sử chúng ta có một mảng được gọi là nums với các giá trị duy nhất từ ​​phạm vi [0, n - 1]. Mảng này không được sắp xếp. Chúng ta cũng có một mảng cặp khác trong đó mỗi cặp chứa các chỉ số nơi các phần tử của mảng có thể được hoán đổi. Chúng ta có thể hoán đổi nhiều lần. Chúng ta phải kiểm tra xem chúng ta có thể sắp xếp mảng theo thứ tự đã sắp xếp bằng cách sử dụng các hoán đổi này hay không.

Vì vậy, nếu đầu vào giống như cặp nums =[6,1,7,3,0,5,4,2] =[(0,4), (6,0), (2,7)], thì đầu ra sẽ là True, vì chúng ta có thể hoán đổi chỉ số (2,7) mảng sẽ là [6,1,2,3,0,5,4,7], sau đó hoán đổi (6,0), mảng sẽ là [4, 1,2,3,0,5,6,7], sau đó hoán đổi (0,4) để lấy [0,1,2,3,4,5,6,7].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=kích thước của nums, P:=số lượng cặp trong mảng cặp
• v:=một danh sách với N số lượng danh sách phụ
• đã thăm:=một tập hợp mới
• đối với tôi trong phạm vi từ 0 đến P, thực hiện
  • chèn chỉ mục thứ hai của cặp [i] vào v [chỉ mục đầu tiên của cặp [i]]
  • chèn chỉ mục đầu tiên của các cặp [i] vào v [chỉ mục thứ hai của các cặp [i]]
• đối với tôi trong phạm vi từ 0 đến N, thực hiện
  • nếu tôi không được đến thăm, thì
    • que:=một hàng đợi kết thúc kép
    • arr_first:=một danh sách mới
    • arr_second:=một danh sách mới
    • đánh dấu tôi là đã ghé thăm
    • chèn tôi vào cuối hàng
    • trong khi hàng không trống, hãy thực hiện
      • u:=phần tử phía trước của hàng và xóa phần tử phía trước của hàng
      • chèn u vào cuối arr_first
      • chèn nums [u] vào cuối arr_second
      • đối với mỗi s trong v [u], thực hiện
        • nếu s không được truy cập, thì
          • đánh dấu là đã ghé thăm
          • chèn s vào cuối hàng
    • arr_first:=sắp xếp danh sách arr_first
    • arr_second:=sắp xếp danh sách arr_second
    • nếu arr_first không giống với arr_second, thì
      • trả về Sai
• trả về True

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Mã mẫu

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))

Đầu vào

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

Đầu ra

True