पायथन में एक स्वैप के साथ पिछला क्रमपरिवर्तन

मान लीजिए कि हमारे पास सकारात्मक पूर्णांकों की एक सरणी ए है (जरूरी नहीं कि अद्वितीय), हमें लेक्सिकोग्राफिक रूप से सबसे बड़ा क्रमपरिवर्तन खोजना है जो ए से छोटा है, जिसे एक स्वैप के साथ बनाया जा सकता है (ए स्वैप दो नंबर ए [i] की स्थिति का आदान-प्रदान करता है और ए [जे])। यदि यह संभव नहीं है, तो उसी सरणी को वापस करें। तो अगर सरणी [3,2,1] की तरह है, तो आउटपुट [3,1,2] होगा, 2 और 1 को स्वैप करके

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=A का आकार
• बाईं ओर n - 2 से नीचे -1 के लिए
  • यदि बायां =-1 है, तो ए वापस करें, अन्यथा जब ए [बाएं]> ए [बाएं + 1], फिर तोड़ दें
• तत्व:=0, अनुक्रमणिका:=0
• बाएं से दाएं + 1 से n के लिए
  • यदि A[दाएं] तत्व, तो
    • तत्व =ए[दाएं]
    • सूचकांक:=दाएं
• स्वैप A[बाएं] और A[सूचकांक]
• वापसी ए

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):
   def prevPermOpt1(self, A):
      n = len(A)
      for left in range(n-2,-2,-1):
         if left == -1:
            return A
         elif A[left]>A[left+1]:
            break
      element = 0
      index = 0
      for right in range(left+1,n):
         if A[right]<A[left] and A[right]>element:
            element = A[right]
            index = right
      temp = A[left]
      A[left] = A[index]
      A[index] = temp
      return A
ob = Solution()
print(ob.prevPermOpt1([4,2,3,1,3]))

इनपुट

[4,2,3,1,3]

आउटपुट

[4, 2, 1, 3, 3]