Python의 다음 순열

다음 순열 방법을 구현하려고 한다고 가정합니다. 이 방법은 숫자를 사전순으로 다음으로 큰 숫자 순열로 재정렬합니다. 이러한 정렬이 불가능한 경우 이 메서드는 가능한 가장 낮은 순서로 재배열합니다(즉, 실제로는 오름차순으로 정렬됨). 교체는 제자리에 있어야 하며 추가 메모리를 사용하지 마십시오. 예를 들어 입력이 왼쪽 열에 있고 해당 출력이 오른쪽 열에 있는 경우

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

단계를 살펴보겠습니다 -

• 찾음 :=false, i :=배열의 길이 – 2
• 동안 나는>=0
  • if A[i]
  • i를 1 증가
• 찾으면 :=false, 배열 A 정렬,
• 그렇지 않으면
  • m :=인덱스 i + 1, A 및 현재 요소 A[i]에서 최대 요소 인덱스 찾기
  • 요소 A[i]와 A[m] 교체
  • i+1에서 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]))

입력

[1,2,5,4,3]

출력

[1, 3, 2, 4, 5]