Pythonでリストの全順列を生成する方法【再帰とバックトラック解説】

Pythonで順列（Permutation）を求める問題とは

重複しない整数からなるコレクションが与えられたとき、そのすべての順列（並べ替えの組み合わせ）を求めることを考えます。

たとえば、配列が [2, 1, 3] の場合、期待される結果は次の6通りです。

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

n個の異なる要素に対する順列の総数は n!（階乗）になるため、3要素なら 3! = 6通り、4要素なら 4! = 24通りの結果が得られます。

解決の手順：再帰とバックトラック

この問題は、再帰とバックトラックを組み合わせることで効率的に解くことができます。以下の手順に従います。

• 再帰的なアプローチを採用し、対象リスト、開始位置（start）、現在構築中の順列（curr）、結果格納用リスト（res）を管理します。
• start が「リストの長さ − 1」より大きくなったら、完成した curr を res に追加して処理を終了します。
• i を start から「リストの長さ − 1」までループさせます。
  • インデックス start と (start + (i − start)) の位置にある要素を入れ替えます。
  • permutation(list, start + 1, curr + [list[start]], res) を再帰呼び出しします。
  • もう一度同じ位置の要素を入れ替えて、元の状態に戻します（バックトラック）。
• 最初に permutation(arr, 0, [], res) を呼び出して探索を開始します。

Pythonでの実装例

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

class Solution(object):
    def permute(self, nums):
        result = []
        self.permute_util(nums, 0, [], result)
        return result

    def permute_util(self, given_list, start, curr, result):
        if start > len(given_list) - 1:
            result.append(curr)
            return
        for i in range(start, len(given_list)):
            self.swap(given_list, start, start + (i - start))
            self.permute_util(given_list, start + 1, curr + [given_list[start]], result)
            self.swap(given_list, start, start + (i - start))

    def swap(self, nums, index1, index2):
        temp = nums[index1]
        nums[index1] = nums[index2]
        nums[index2] = temp

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

入力

[1,2,3,4]

出力

[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]

補足：itertools.permutationsを使った簡潔な方法

標準ライブラリの itertools を利用すると、同じ結果をわずか数行で得られます。

from itertools import permutations

nums = [1, 2, 3, 4]
result = [list(p) for p in permutations(nums)]
print(result)

競技プログラミングやアルゴリズムの学習では、再帰による自前実装が仕組みの理解に役立ちます。一方、実務のコードでは itertools.permutations を活用する方が簡潔でバグも起きにくいためおすすめです。