Hoán vị (Permutations) trong Python

Giả sử chúng ta có một tập hợp các số nguyên khác nhau; chúng ta phải tìm tất cả các hoán vị có thể. Ví dụ, nếu mảng là [2,1,3], 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, chúng ta làm theo các bước sau:

• Sử dụng phương pháp đệ quy, tạo danh sách, start, curr và res.
• Nếu start > độ dài danh sách - 1, thêm curr vào res, và trả về.
• Với i từ start đến độ dài danh sách cho trước - 1:
  • Hoán đổi các phần tử của danh sách tại chỉ số start và start + (i - start).
  • Gọi permutation(list, start + 1, curr + [list[start]], res).
  • Hoán đổi lại các phần tử tại chỉ số start và start + (i - start).
  • Ban đầu gọi permutation(arr, 0, [], res).

Ví dụ (Python)

Xem 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:
            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)
            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]]