Hoán vị trước đó với một lần hoán đổi trong Python

Giả sử có mảng A số nguyên dương (không nhất thiết duy nhất), ta phải tìm hoán vị lớn nhất theo thứ tự từ điển mà nhỏ hơn A, có thể đạt được bằng một lần hoán đổi (hoán đổi vị trí A[i] và A[j]). Nếu không thể, trả về mảng gốc. Nếu mảng [3,2,1], kết quả [3,1,2] bằng cách hoán đổi 2 và 1.

Để giải quyết, ta làm theo các bước −

• n := độ dài A
• với left từ n-2 xuống -1
  • nếu left = -1, trả về A, ngược lại nếu A[left] > A[left+1], break
• element := 0, index := 0
• với right từ left+1 đến n
  • nếu A[right] < A[left] và A[right] > element
    • element = A[right]
    • index := right
• hoán đổi A[left] và A[index]
• trả về A

Xem triển khai sau −

Ví dụ

class Solution(object):    def prevPermOpt1(self, A):       n = len(A)       for left in range(n-2,-2,-1):          if left == -1:             return A          elif A[left]>A[left+1]:             break       element = 0       index = 0       for right in range(left+1,n):          if A[right]<A[left] and A[right]>element:             element = A[right]             index = right       temp = A[left]       A[left] = A[index]       A[index] = temp       return A ob = Solution() print(ob.prevPermOpt1([4,2,3,1,3]))

Đầu vào

[4,2,3,1,3]

Kết quả

[4, 2, 1, 3, 3]