मान लीजिए हम नेक्स्ट पर्मुटेशन विधि को लागू करना चाहते हैं, वह विधि संख्याओं को संख्याओं के लेक्सिकोग्राफिक रूप से अगले बड़े क्रमचय में पुनर्व्यवस्थित करती है। यदि ऐसी व्यवस्था संभव नहीं है, तो यह विधि इसे न्यूनतम संभव क्रम में पुनर्व्यवस्थित करेगी (वह वास्तव में आरोही क्रम में सॉर्ट किया गया है)। प्रतिस्थापन इन-प्लेस होना चाहिए और कोई अतिरिक्त मेमोरी उपयोग नहीं करनी चाहिए। उदाहरण के लिए, यदि इनपुट बाएं कॉलम में हैं और उनके संबंधित आउटपुट दाएं कॉलम में हैं।
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] < A[i + 1], तो found := True, और लूप समाप्त करें
- i को 1 से बढ़ाएं
- यदि found := 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]