Hoán vị tiếp theo trong Python

Giả sử chúng ta muốn triển khai phương thức hoán vị tiếp theo, phương thức này sắp xếp lại các số thành hoán vị lớn hơn về mặt từ điển. Nếu không thể sắp xếp như vậy, phương thức sẽ sắp xếp lại theo thứ tự thấp nhất có thể (tức là sắp xếp tăng dần). Thay thế phải thực hiện tại chỗ (in-place) và không sử dụng bộ nhớ thêm. Ví dụ:

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Các bước thực hiện

• found := false, i := độ dài mảng - 2.
• Khi i >= 0:
  • Nếu A[i] < A[i + 1], thì found := True, thoát vòng lặp.
  • Giảm i đi 1.
• Nếu found := false, sắp xếp mảng A.
• Ngược lại:
  • m := tìm chỉ số phần tử lớn nhất từ chỉ số i + 1 trong A, và lớn hơn A[i].
  • Hoán đổi A[i] và A[m].
  • Đảo ngược tất cả phần tử từ i+1 đến cuối trong A.

Ví dụ minh họa

class Solution(object):
    def nextPermutation(self, nums):
        found = False
        i = len(nums) - 2
        while i >= 0:
            if nums[i] < nums[i+1]:
                found = True
                break
            i -= 1
        if not found:
            nums.sort()
        else:
            m = self.findMaxIndex(i+1, nums, nums[i])
            nums[i], nums[m] = nums[m], nums[i]
            nums[i+1:] = nums[i+1:][::-1]
        return nums

    def findMaxIndex(self, index, a, curr):
        ans = -1
        index = 0
        for i in range(index, len(a)):
            if a[i] > curr:
                if ans == -1:
                    ans = curr
                    index = i
                else:
                    ans = min(ans, a[i])
                    index = i
        return index

ob1 = Solution()
print(ob1.nextPermutation([1,2,5,4,3]))

Đầu vào

[1,2,5,4,3]

Đầu ra

[1, 3, 2, 4, 5]