पायथन में अगला क्रमपरिवर्तन

मान लीजिए कि हम अगली क्रमपरिवर्तन पद्धति को लागू करना चाहते हैं, तो वह विधि संख्याओं को लेक्सिकोग्राफिक रूप से संख्याओं के अगले बड़े क्रमपरिवर्तन में पुनर्व्यवस्थित करती है। यदि ऐसी व्यवस्था संभव नहीं है, तो यह विधि इसे न्यूनतम संभव क्रम के रूप में पुनर्व्यवस्थित करेगी (अर्थात, आरोही क्रम में क्रमबद्ध)। प्रतिस्थापन जगह पर होना चाहिए और किसी भी अतिरिक्त मेमोरी का उपयोग नहीं करना चाहिए। उदाहरण के लिए, यदि इनपुट बाएं हाथ के कॉलम में हैं और इसके संबंधित आउटपुट दाएं हाथ के कॉलम में हैं।

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

आइए चरणों को देखें -

• पाया गया:=झूठा, i:=सरणी की लंबाई – 2
• जबकि मैं>=0
  • अगर A[i]
  • मैं 1 से बढ़ाएँ
• यदि पाया जाता है :=असत्य, तो सरणी 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]