Pythonで1回のスワップで求める「直前の順列」（辞書順で最大の小さい順列）

問題の概要

正の整数からなる配列A（要素は重複していても構いません）が与えられます。この配列に対して、たった1回のスワップ（2つの要素A[i]とA[j]の位置を入れ替える操作）によって作れる順列のうち、Aよりも辞書順に小さく、かつそのような順列の中で最も大きいものを見つける必要があります。条件を満たす順列が存在しない場合は、元の配列をそのまま返します。

例えば、配列が [3, 2, 1] の場合、2と1を入れ替えることで [3, 1, 2] という出力が得られます。

解法のステップ

• n := 配列Aの長さ
• left を n−2 から −1 へと降順にループする
  • left == −1 になったら A をそのまま返す
  • A[left] > A[left+1] を満たした時点でループを抜ける
• element := 0、index := 0 で初期化する
• right を left+1 から n−1 までループする
  • A[right] < A[left] かつ A[right] > element の場合
    • element = A[right]
    • index := right
• A[left] と A[index] をスワップする
• 配列Aを返す

なぜこの方法でうまくいくのか

辞書順で「ひとつ前」の順列を作る鍵は、配列を後ろから走査して昇順が初めて崩れる位置を見つけることです。その位置 left では A[left] > A[left+1] が成り立ち、left より右側はすべて昇順に並んでいます。ここで、A[left] より小さい値のうち最大のものと入れ替えれば、先頭部分はそのまま維持しつつ末尾だけを最適化できるため、「元の配列より小さいが、可能な限り大きい」順列が得られます。

また、候補となる最大値が複数存在する場合は、より左側にあるものと交換したほうが結果は大きくなります（例：[3,1,1] なら [1,3,1] の方が [1,1,3] より大きい）。上記のコードでは更新条件が厳密な「>」になっているため、同じ値が複数あっても自動的に最初の出現位置が選ばれます。

実装例

class Solution(object):
    def prevPermOpt1(self, A):
        n = len(A)
        # 後ろから、A[left] > A[left+1] となる位置を探す
        for left in range(n-2, -2, -1):
            if left == -1:
                return A
            elif A[left] > A[left+1]:
                break
        # A[left] 未満の値のうち最大のものを探す
        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]

この例では、インデックス2（値3）が昇順が崩れる位置となり、右側にある3未満の値のうち最大である1（インデックス3）と入れ替わるため、結果は [4, 2, 1, 3, 3] になります。