Next Permutation ใน Python - หาการเรียงต่อไปแบบ Lexicographic

เราต้องการใช้เมธอด nextPermutation ที่จัดเรียงตัวเลขใหม่เป็น permutation ถัดไปแบบ lexicographically greater หากไม่สามารถจัดได้ ให้จัดเรียงใหม่เป็นลำดับน้อยที่สุด (เรียงจากน้อยไปมาก) ต้องทำในที่เดิม (in-place) ไม่ใช้หน่วยความจำเพิ่ม ตัวอย่าง:

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

ขั้นตอนการทำงาน

1. found := false, i := length of array - 2
2. วนลูป while i >= 0:
   • ถ้า A[i] < A[i+1] ให้ found := True และออกจากลูป
   • ลด i ลง 1
3. ถ้า found == false ให้เรียงลำดับอาร์เรย์ A
4. มิฉะนั้น:
   • 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]