পাইথনে এক সোয়াপ দিয়ে প্রিভিয়াস পারমুটেশন বের করুন

একটি পজিটিভ ইন্টিজার অ্যারে 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]