📊

【重複順列の全列挙】~ 手書きからライブラリ使用まで ~

2025/07/28に公開

はじめに

本記事のテーマは、重複あり順列の全列挙です！
今までは深さ優先探索で列挙していたのですが、便利なライブラリ（product）を見つけたので、手書き実装からライブラリ実装まで考えます。

やりたいこと

li = [1,2,3]を与えられたとき、
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],...
3 x 3 x 3 = 27の要素がありこれを列挙したい！
イメージ

実装（手書き）

手書き実装では深さ優先探索で列挙を行います。
上の図を、再帰で忠実に再現していきます。

# 深さ優先探索（depth first search）
def dfs(elements,length): 
    if length == 3:          
        ans.append(elements) 
    else:
        for e in li:
            dfs(elements+[e],length+1)

li = [1,2,3]
ans = []
dfs([],0)
print(ans)

出力

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

実装（ライブラリ）

次にライブラリを使用した実装をします。productを使います。

from itertools import product

li = [1,2,3]
ans = list(product(li,repeat=3)) 
print(ans)

出力

[(1, 1, 1), (1, 1, 2), (1, 1, 3), 
 (1, 2, 1), (1, 2, 2), (1, 2, 3), 
 ... 
 (3, 3, 1), (3, 3, 2), (3, 3, 3)]

[1,2,3]を３つ用意してそこから１つずつ選んで、新たな組み合わせを構成しています（直積）。

手書き（超省略）

記事を書いている途中でこんな書き方もあると知りました。要素のサイズが小さければこれで十分ですね...。

li = [1,2,3]
ans = [(x,y,z) for x in li for y in li for z in li]
print(ans)

出力

[(1, 1, 1), (1, 1, 2), (1, 1, 3), 
 (1, 2, 1), (1, 2, 2), (1, 2, 3), 
 ... 
 (3, 3, 1), (3, 3, 2), (3, 3, 3)]

最後に

競技プログラミングをやっていると、そこそこの頻度で出現するので実装・ライブラリの整理ができて良かったです！このitertoolsには、順列列挙、組み合わせなど便利なライブラリがあるのでこれからどんどん使っていきます！

最後まで読んでいただきありがとうございました！