Pythonでの1つのスワップによる以前の順列

正の整数（必ずしも一意ではない）の配列Aがあるとすると、1回のスワップで作成できるAよりも小さい辞書式順序で最大の順列を見つける必要があります（Aスワップは2つの数値A[i]とA [j]）。不可能な場合は、同じ配列を返します。したがって、配列が[3,2,1]のような場合、2と1を交換することにより、出力は[3,1,2]になります

これを解決するには、次の手順に従います-

• n：=Aのサイズ
• 範囲n–2から-1までの左側
  • left =-1の場合は、Aを返します。それ以外の場合は、A [left]> A [left + 1]の場合、中断します
• 要素：=0、インデックス：=0
• 右の場合は左+1からn
  • A [right] 要素の場合、
    • 要素=A[右]
    • インデックス：=右
• 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]