পাইথনে পরবর্তী পারমুটেশন

ধরুন আমরা পরবর্তী পারমুটেশন পদ্ধতিটি বাস্তবায়ন করতে চাই, সেই পদ্ধতিটি সংখ্যাকে লেক্সিকোগ্রাফিকভাবে পরবর্তী বৃহত্তর সংখ্যার পারমুটেশনে পুনর্বিন্যাস করে। যদি এই ধরনের ব্যবস্থা সম্ভব না হয়, এই পদ্ধতিটি সম্ভাব্য সর্বনিম্ন ক্রম হিসাবে এটিকে পুনর্বিন্যাস করবে (এটি আসলে, আরোহী ক্রমে সাজানো)। প্রতিস্থাপন অবশ্যই জায়গায় হতে হবে এবং কোনো অতিরিক্ত মেমরি ব্যবহার করবেন না। উদাহরণস্বরূপ, যদি ইনপুটগুলি বাম হাতের কলামে থাকে এবং এর সংশ্লিষ্ট আউটপুটগুলি ডান হাতের কলামে থাকে৷

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

আসুন ধাপগুলো দেখি -

• found :=false, i :=অ্যারের দৈর্ঘ্য – 2
• যখন i>=0
  • যদি A[i]
  • i 1 দ্বারা বাড়ান
• যদি পাওয়া যায় :=মিথ্যা, তারপর অ্যারে সাজান,
• অন্যথায়
  • m :=সূচক i + 1, A থেকে এবং বর্তমান উপাদান A[i] থেকে সর্বাধিক উপাদান সূচক খুঁজুন
  • এ[i] এবং A[m] উপাদানগুলিকে অদলবদল করুন
  • এতে i+1 থেকে শেষ পর্যন্ত সমস্ত উপাদানকে বিপরীত করুন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]