RSSフィードを購読
【Python 雑談・雑学 + coding challenge】itertools モジュールの combinations() メソッドを自分で実装してみよう！ 投稿一覧へ戻る
Published 2020年9月1日17:01 by mootaro23
SUPPORT UKRAINE
- Your indifference to the act of cruelty can thrive rogue nations like Russia -
さて、itertools モジュールの combinations() メソッドを使ったことがありますか？
シーケンス要素の「組み合わせ」を返してくれます。
さて、いかがだったでしょうか？ 私の周辺では悩んでいる方が結構いました。
Python ドキュメントの itertools モジュール combinations() の説明欄 にもこの関数と等価である実装方法の例が載っています。
そちらでは while の無限ループを利用した generator 関数としての例を挙げていますので、こちらでは再帰関数 ( recursive function ) としての実装方法を挙げてみたいと思います。
再帰を文に書いて説明しようとすると逆にワケが分からなくなっちゃいますから詳細は省きます。ただ、
# 1: 最下層では空のタプルを要素に持つリスト [()] が返ってくる、
# 2: それぞれの層では、下の層から戻ってきたリストの要素であるタプルを一度アンパックして、その層の要素を付け加えた新しいタプルを作っている、
という 2 点がこの実装のミソとなっております。
シーケンス要素の「組み合わせ」を返してくれます。
from itertools import combinations
nums = [0, 1, 2, 3]
print(list(combinations(nums, 2)))
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(list(combinations(nums, 3)))
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
print(list(combinations(nums, 4)))
# [(0, 1, 2, 3)]
print(list(combinations(nums, 5)))
# []
nums = [0, 1, 2, 3]
print(list(combinations(nums, 2)))
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(list(combinations(nums, 3)))
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
print(list(combinations(nums, 4)))
# [(0, 1, 2, 3)]
print(list(combinations(nums, 5)))
# []
問題 ( 制限時間: 60 分 ):
今回の coding challenge はこの combinations() メソッドの自分なりの実装です。
ヒント:
combinations() に渡す第 2 引数が 2 の場合であれば、
combinations() に渡す第 2 引数が 3 の場合であれば、
と表すことが可能ですが、第 2 引数の値が変化すれば for 文のネストの深さも変化しますから、最初から決め打ちで実装しておくことは出来ませんョ！
それと、combinations() メソッドと同様、返り値はタプルのリスト、でなければいけません。
では、チャレンジ！
今回の coding challenge はこの combinations() メソッドの自分なりの実装です。
ヒント:
combinations() に渡す第 2 引数が 2 の場合であれば、
result = []
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
result.append((i, j))
print(result)
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
result.append((i, j))
print(result)
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
combinations() に渡す第 2 引数が 3 の場合であれば、
result = []
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
result.append((i, j, k))
print(result)
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
result.append((i, j, k))
print(result)
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
と表すことが可能ですが、第 2 引数の値が変化すれば for 文のネストの深さも変化しますから、最初から決め打ちで実装しておくことは出来ませんョ！
それと、combinations() メソッドと同様、返り値はタプルのリスト、でなければいけません。
では、チャレンジ！
さて、いかがだったでしょうか？ 私の周辺では悩んでいる方が結構いました。
Python ドキュメントの itertools モジュール combinations() の説明欄 にもこの関数と等価である実装方法の例が載っています。
そちらでは while の無限ループを利用した generator 関数としての例を挙げていますので、こちらでは再帰関数 ( recursive function ) としての実装方法を挙げてみたいと思います。
def my_combinations(iterable, r):
if r == 0:
return [()] # 1:
result = []
for i in range(len(iterable)):
m = iterable[i]
for n in my_combinations(iterable[i + 1:], r - 1):
result.append((m, *n)) # 2:
return result
print(my_combinations(nums, 2))
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(my_combinations(nums, 3))
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
print(my_combinations(nums, 4))
# [(0, 1, 2, 3)]
print(my_combinations(nums, 5))
# []
if r == 0:
return [()] # 1:
result = []
for i in range(len(iterable)):
m = iterable[i]
for n in my_combinations(iterable[i + 1:], r - 1):
result.append((m, *n)) # 2:
return result
print(my_combinations(nums, 2))
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(my_combinations(nums, 3))
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
print(my_combinations(nums, 4))
# [(0, 1, 2, 3)]
print(my_combinations(nums, 5))
# []
再帰を文に書いて説明しようとすると逆にワケが分からなくなっちゃいますから詳細は省きます。ただ、
# 1: 最下層では空のタプルを要素に持つリスト [()] が返ってくる、
# 2: それぞれの層では、下の層から戻ってきたリストの要素であるタプルを一度アンパックして、その層の要素を付け加えた新しいタプルを作っている、
という 2 点がこの実装のミソとなっております。
この記事に興味のある方は次の記事にも関心を持っているようです...
- People who read this article may also be interested in following articles ... -