การเปลี่ยนลำดับถัดไปใน Python

สมมติว่าเราต้องการใช้วิธีการเรียงสับเปลี่ยนถัดไป วิธีการนั้นจะจัดเรียงตัวเลขใหม่เป็นการเรียงสับเปลี่ยนตัวเลขถัดไปที่มากขึ้น หากไม่สามารถจัดเรียงได้ วิธีนี้จะจัดเรียงใหม่เป็นลำดับที่ต่ำที่สุดเท่าที่จะเป็นไปได้ (ที่จริงแล้ว เรียงลำดับจากน้อยไปหามาก) การเปลี่ยนจะต้องเข้าที่และไม่ใช้หน่วยความจำเพิ่มเติม ตัวอย่างเช่น หากอินพุตอยู่ในคอลัมน์ด้านซ้ายและเอาต์พุตที่สอดคล้องกันอยู่ในคอลัมน์ด้านขวา

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

ให้เราดูขั้นตอน -

• พบ :=false, i :=ความยาวของอาร์เรย์ – 2
• ในขณะที่ i>=0
  • ถ้า 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]