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

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

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

• n := A का आकार
• left के लिए n - 2 से -1 तक नीचे की रेंज में
  • यदि left = -1, तो A लौटाएं, अन्यथा जब A[left] > A[left + 1], तो ब्रेक करें
• element := 0, index := 0
• right के लिए left + 1 से n तक की रेंज में
  • यदि A[right] < A[left] और A[right] > element, तो
    • element = A[right]
    • index := right
• A[left] और A[index] को स्वैप करें
• 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]