Giả sử chúng ta có một tập hợp các số nguyên riêng biệt; chúng ta phải tìm tất cả các hoán vị có thể có. Vì vậy, nếu mảng giống như [2,1,3], thì kết quả sẽ là [[1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [3,1,2], [3,2,1]]
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
- Chúng tôi sẽ sử dụng phương pháp đệ quy, điều này sẽ tạo danh sách, bắt đầu, thu gọn và thay đổi lại
- if start> length of list - 1, sau đó thêm curr vào res và trả về
- cho tôi trong phạm vi bắt đầu từ độ dài của danh sách đã cho - 1
- hoán đổi các phần tử của danh sách hiện tại khi bắt đầu chỉ mục và (bắt đầu + (i - bắt đầu))
- hoán vị (danh sách, bắt đầu + 1, curr + [danh sách [bắt đầu]], res)
- hoán đổi các phần tử của danh sách hiện tại khi bắt đầu chỉ mục và (bắt đầu + (i - bắt đầu))
- ban đầu gọi hoán vị (arr, 0, [], res)
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object): def permute(self, nums): result = [] self.permute_util(nums,0,[],result) return result def permute_util(self,given_list,start,curr,result): if start > len(given_list)-1: #print(curr) result.append(curr) return for i in range(start,len(given_list)): self.swap(given_list,start,start+(i-start)) self.permute_util(given_list,start+1,curr+[given_list[start]],result) #print(given_list) self.swap(given_list, start, start + (i - start)) def swap(self,nums,index1,index2): temp = nums[index1] nums[index1] = nums[index2] nums[index2] = temp ob1 = Solution() print(ob1.permute([1,2,3,4]))
Đầu vào
[1,2,3,4]
Đầu ra
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]