Đó là một bài tập nhỏ thú vị để thuyết phục bản thân rằng quy trình trên thực sự hiệu quả. Hãy nhớ rằng toán tử XOR có tính chất giao hoán và
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Một cách khác là sử dụng các toán tử cộng và trừ
>>> a, b = 5, 20
>>> a = a + b
>>> b = a - b
>>> a = a - b
>>> a, b
[20, 5]
Lưu ý rằng hai thủ tục trên chỉ hoạt động khi
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Hoán đổi hai mục trong một mảng
Đưa ra một danh sách
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Xáo trộn một mảng
Cho một mảng, viết chương trình tạo hoán vị ngẫu nhiên các phần tử của mảng
Xáo trộn Fisher–Yates là một thuật toán nổi tiếng để giải quyết vấn đề này. Trong mã giả, thuật toán hoạt động như sau
Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách hoán đổi hai phần tử tại các vị trí nhất định trong Danh sách. Hoán đổi có nghĩa là trao đổi các giá trị của hai số. Bài trước chúng ta đã học cách hoán đổi phần tử đầu và phần tử cuối của một danh sách. Chương trình này cũng tương tự như vậy, chỉ khác là người dùng sẽ chỉ định vị trí của các phần tử cần đổi chỗ. Chương trình sẽ trả về và hiển thị danh sách hoán đổi
Nhìn vào các ví dụ để hiểu định dạng đầu vào và đầu ra
Đầu vào. [1, 2, 8, 9, 3, 0, 7] pos1=2 pos2=4
đầu ra. [1, 9, 8, 2, 3, 0, 7]
Tiếp cận
Để thực hiện nhiệm vụ này, chúng ta có thể làm theo nhiều cách tiếp cận, một số được thảo luận bên dưới-
- Bằng cách sử dụng biến thứ ba để hoán đổi các giá trị có tại các chỉ mục đã cho
- Bằng cách sử dụng trao đổi trực tiếp
- Bằng cách sử dụng hàm pop[] để bật các phần tử tại vị trí đã cho
Chúng tôi sẽ thảo luận chi tiết cả ba cách tiếp cận một cách riêng biệt
Cách tiếp cận 1. Hoán đổi sử dụng biến thứ ba
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một biến thứ ba để hoán đổi các giá trị hiện tại ở vị trí đã cho
Logic đằng sau việc hoán đổi hai số bằng biến thứ ba là
Lưu trữ giá trị của biến đầu tiên trong biến thứ ba
Lưu trữ giá trị của biến thứ hai trong biến đầu tiên
Cuối cùng, lưu trữ giá trị của biến thứ ba trong biến thứ hai
Nếu, var1 là biến đầu tiên và var2 là biến thứ hai và temp là biến thứ ba sẽ giữ giá trị của var1, mã để hoán đổi là,
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Bây giờ, chúng ta sẽ xem xét thuật toán để hiểu cách triển khai của phương pháp
thuật toán
Bước 1- Xác định hàm hoán đổi các phần tử với danh sách sl và vị trí pos1 và pos2 làm tham số
Bước 2- Hoán đổi các phần tử sl[pos1] và sl[pos2] bằng biến thứ ba
Bước 3- Trả lại danh sách đã hoán đổi
Bước 4- Xác định giá trị danh sách và vị trí của các phần tử cần hoán đổi
Bước 5- Truyền danh sách và [pos1-1] và [pos2-1] vào hàm [vì việc lập chỉ mục bắt đầu từ 0] và in kết quả
Chương trình Python 1
Nhìn vào chương trình hoàn chỉnh được đưa ra dưới đây để hoán đổi các phần tử ở chỉ số 0 và chỉ số n-1
#swap two elements in list
# Swap function
def swapList[sl,pos1,pos2]:
n = len[sl]
# Swapping
temp = sl[pos1]
sl[pos1] = sl[pos2]
sl[pos2] = temp
return sl
l= [10, 14, 5, 9, 56, 12]
pos1= 2
pos2= 5
print[l]
print["Swapped list: ",swapList[l,pos1-1,pos2-1]]
[10, 14, 5, 9, 56, 12]
Đã hoán đổi danh sách. [10, 56, 5, 9, 14, 12]
Cách tiếp cận 2. Trao đổi bằng cách sử dụng lập chỉ mục
Theo cách tiếp cận này, chúng ta sẽ hoán đổi trực tiếp các giá trị tại chỉ mục đã cho
Trong Python, chúng ta có thể hoán đổi trực tiếp hai biến a và b mà không cần sử dụng biến thứ ba bằng mã-
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Nhìn vào thuật toán để hiểu hoạt động của chương trình
thuật toán
Bước 1- Xác định một hàm sẽ hoán đổi các giá trị
Bước 2- Hoán đổi các phần tử tại chỉ mục pos1 và pos2
Bước 3- Trả lại danh sách đã hoán đổi
Bước 4- Khai báo các giá trị liệt kê và chỉ vị trí các phần tử cần đổi chỗ
Bước 5- Truyền danh sách và các vị trí trong hàm và hiển thị kết quả
Chương trình Python 2
Nhìn vào chương trình hoàn chỉnh được đưa ra dưới đây
________số 8
[9, 11, 5, 3, 6, 27, 4]
Danh sách đã hoán đổi. [9, 11, 6, 3, 5, 27, 4]
Cách tiếp cận 3. Hoán đổi sử dụng hàm pop[]
Trong cách tiếp cận này, chúng ta sẽ sử dụng hàm pop[] là hàm tích hợp sẵn trong Python. Nó xóa và trả về giá trị tại chỉ mục đã cho từ danh sách. Nếu chỉ mục không được cung cấp thì nó sẽ xóa và trả về phần tử cuối cùng. Chúng ta sẽ sử dụng hàm pop[] để loại bỏ các phần tử tại vị trí đã cho khỏi danh sách và lưu trữ chúng trong các biến riêng biệt
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
[20, 5]
Chúng tôi sẽ sử dụng insert[] và append[] là các hàm danh sách thường được sử dụng để lưu trữ lại các phần tử theo thứ tự đã hoán đổi trong danh sách
Nhìn vào thuật toán để hiểu chương trình
thuật toán
Bước 1- Xác định hàm hoán đổi các phần tử với danh sách và vị trí pos1 và pos2 làm tham số
Bước 2- Lưu trữ phần tử đầu tiên trong một biến trước bằng cách sử dụng pop[pos1]
Bước 3- Lưu trữ phần tử thứ hai trong biến thứ hai bằng cách sử dụng pop[pos2-1]
Bước 4- Hiện tại danh sách sẽ có n-2 phần tử
Bước 5- Chèn hai phần tử đã bật vào vị trí của chúng
Bước 6- insert[pos1,second] sẽ lưu phần tử thứ hai vào vị trí của phần tử đầu tiên
Bước 7- insert[pos2,first] sẽ chèn phần tử đầu tiên vào vị trí của phần tử thứ hai
Bước 8- Trả lại danh sách đã hoán đổi
Bước 9- Khai báo danh sách và truyền danh sách, vị trí vào hàm
Bước 10- In danh sách được hàm trả về
Chương trình
Nhìn vào chương trình hoàn chỉnh được đưa ra dưới đây để hiểu việc thực hiện phương pháp
#swap two element in list
# Swap function
def swapPositions[list, pos1, pos2]:
# popping both the elements from list
first = list.pop[pos1]
second = list.pop[pos2-1]
# inserting in each others positions
list.insert[pos1, second]
list.insert[pos2, first]
return list
# Driver function
List = [2, 6, 12, 23, 8, 9]
pos1, pos2 = 1, 3
print[List]
print["Swapped list: ",swapPositions[List, pos1-1, pos2-1]]
[2, 6, 12, 23, 8, 9]
Đã hoán đổi danh sách. [12, 6, 2, 23, 8, 9]
Phần kết luận
Trong hướng dẫn này, chúng ta đã học được ba cách hoán đổi hai phần tử khi danh sách và vị trí của các phần tử được đưa ra. Chúng ta đã thảo luận về cách hoán đổi bằng cách sử dụng biến thứ ba, bằng cách hoán đổi trực tiếp các phần tử tại các chỉ mục đã cho và bằng cách sử dụng hàm pop[]