Pythonで実装する「次の順列（Next Permutation）」アルゴリズムの解説

「次の順列（Next Permutation）」とは、数列を辞書式順序で次に大きい並びへと並べ替える操作のことです。もし次に大きい順列が存在しない場合（数列が降順に並んでいる場合）は、最も小さい順列、つまり昇順にソートされた状態へと並べ替えます。この処理では余分なメモリを使用せず、配列そのものを直接書き換える「インプレース」方式で実装する必要があります。

入力と出力の対応は以下のようになります。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

アルゴリズムの手順

• found := False、i := 配列の長さ − 2 で初期化する
• i >= 0 の間、以下を繰り返す
  • A[i] < A[i + 1] であれば found := True としてループを終了する
  • i を 1 減らす
• found が False のままの場合、配列 A を昇順にソートする
• それ以外の場合は、以下の処理を行う
  • m := インデックス i + 1 以降の要素の中から、A[i] より大きい値のうち最小のもののインデックスを求める
  • A[i] と A[m] を入れ替える
  • インデックス i + 1 から末尾までの要素をすべて反転させる

このアルゴリズムのポイントは、i 以降の部分が必ず降順（非増加順）になっていることを利用する点です。降順の列の中で「A[i] より大きい要素のうち最も右側にあるもの」は、「A[i] より大きい最小の要素」と一致するため、単純な走査で置き換え対象を特定できます。全体の計算量は O(n) です。

それでは、実際の実装を見てみましょう。

実装例

class Solution(object):
    def nextPermutation(self, nums):
        found = False
        i = len(nums) - 2
        while i >= 0:
            if nums[i] < nums[i + 1]:
                found = True
                break
            i -= 1
        if not found:
            nums.sort()
        else:
            m = self.findMaxIndex(i + 1, nums, nums[i])
            nums[i], nums[m] = nums[m], nums[i]
            nums[i + 1:] = nums[i + 1:][::-1]
        return nums

    def findMaxIndex(self, index, a, curr):
        ans = -1
        index = 0
        for i in range(index, len(a)):
            if a[i] > curr:
                if ans == -1:
                    ans = curr
                    index = i
                else:
                    ans = min(ans, a[i])
                    index = i
        return index

ob1 = Solution()
print(ob1.nextPermutation([1, 2, 5, 4, 3]))

入力

[1,2,5,4,3]

出力

[1, 3, 2, 4, 5]

この例では、[1, 2, 5, 4, 3] の末尾部分 [5, 4, 3] が降順になっています。2（インデックス1）より大きい最小の値である 3 と入れ替えた後、残りの部分を反転することで、[1, 3, 2, 4, 5] という次の順列が得られます。このように、降順の接尾辞を活かすことで、全順列を生成することなく効率的に次の順列を求められます。