【Python基礎】再帰処理を使って全組合せを作ってみる

2023年12月11日2024年1月11日

URLをコピーしました！

再帰処理

前回、多次元のリストやタプルをSet型を使って重複を削除する方法を紹介しました。

あわせて読みたい

【Python基礎】多次元のリストやタプルをSet型を使って重複を削除する方法 Set型前回、Pythonでタプル（tuple）の作成、要素の取得・追加の方法を紹介しました。今回はSet型を使って多次元のリストやタプルの重複を削除する方法を紹介します。…

今回はTurtleで木を描いたときに使った再帰処理をもう少し勉強して、全組み合わせを作るプログラムを書いてみます。

あわせて読みたい

【Turtle】再帰処理を使った木の描き方[Python] Turtle 前回、PythonのグラフィックスライブラリTurtleで菱形、台形（平行四辺形）、星型、葉っぱ型の描き方を紹介しました。今回は「再帰」と言われる処理を使って木…

まずはおさらいからです。

再帰処理とは「プログラム中にそのプログラム自身を呼び出す記述があるプログラム」でした。

ということで例えばこんな感じです。

def count(n):
    if n == 0:
        return
    
    print(n)
    
    count(n-1)
    
count(5)

実行結果
5
4
3
2
1

countという関数の中にcountという関数が使われています。

この際注意することは必ず終了条件をif文で書き、returnで終わらせることです。

再帰処理で全組合せを作るプログラムを作成してみる

今回はもう少し再帰処理を使ってみるために、例として２つの数字を入力し、それぞれの値以下の数字を使って、全組合せを作るプログラムを書いてみます。

ちなみに再帰処理を使わないとこんな感じです。

def count(n, m):
    for i in range(n, 0, -1):
        for j in range(m, 0, -1):
            print(i, j)

count(3, 2)

実行結果
3 2
3 1
2 2
2 1
1 2
1 1

それぞれの数字をrange関数でリストに変換し、for文を使って順に取り出すことによって組合せを作成しています。

で再帰処理を使って作ってみたのがこちら。

data = []

def count(n, m):
    if n == 0 or m == 0:
        return
        
    data.append((n, m))
    
    count(n-1, m)
    count(n, m-1)
    
count(3, 2)

print(data)
print(set(data))

実行結果
[(3, 2), (2, 2), (1, 2), (1, 1), (2, 1), (1, 1), (3, 1), (2, 1), (1, 1)]
{(1, 2), (2, 1), (3, 1), (1, 1), (2, 2), (3, 2)}

解説していくとcount関数には２つの引数nとmが渡されます。

最初に終了条件ですが「if n == 0 or m == 0:」ということでnかmが0になったら終了します。

そしてn、mの数字はタプルとして、dataというリストに格納されます。

ここでなぜタプルにしてあるかというと、前回学んだように二次元目以降はタプルにしておくとその後Set型に変換することで重複を削除できるからです。

あわせて読みたい