Hoán vị tiếp theo trong Python

Giả sử chúng ta muốn thực hiện phương pháp hoán vị tiếp theo, phương pháp đó sắp xếp lại các số thành hoán vị số lớn hơn tiếp theo về mặt từ vựng. Nếu không thể sắp xếp như vậy, phương pháp này sẽ sắp xếp lại theo thứ tự thấp nhất có thể (Thực ra là sắp xếp theo thứ tự tăng dần). Việc thay thế phải được thực hiện tại chỗ và không sử dụng thêm bất kỳ bộ nhớ nào. Ví dụ:nếu Đầu vào ở cột bên trái và đầu ra tương ứng của nó ở cột bên phải.

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

Hãy để chúng tôi xem các bước -

tìm thấy:=false, i:=độ dài của mảng - 2
trong khi tôi> =0
- if A [i]
- tăng tôi lên 1

nếu tìm thấy:=false, thì hãy sắp xếp mảng A,

nếu không thì

m:=tìm chỉ số phần tử tối đa từ chỉ mục i + 1, từ A và từ phần tử hiện tại A [i]
hoán đổi các phần tử A [i] và A [m]
đảo ngược tất cả các phần tử từ i + 1 đến cuối bằng A

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]