【Python 雑談・雑学 + coding challenge】itertools モジュールの combinations() メソッドを自分で実装してみよう! 投稿一覧へ戻る

Tags: recursive , challenge , coding , python , itertools , combinations

Published 2020年9月1日17:01 by T.Tsuyoshi

さて、itertools モジュールの combinations() メソッドを使ったことがありますか?


シーケンス要素の「組み合わせ」を返してくれます。


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)))

# []



問題 ( 制限時間: 60 分 ):


今回の 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)]



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)]



と表すことが可能ですが、第 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))

# []



再帰を文に書いて説明しようとすると逆にワケが分からなくなっちゃいますから詳細は省きます。ただ、


# 1: 最下層では空のタプルを要素に持つリスト [()] が返ってくる、


# 2: それぞれの層では、下の層から戻ってきたリストの要素であるタプルを一度アンパックして、その層の要素を付け加えた新しいタプルを作っている、


という 2 点がこの実装のミソとなっております。

この投稿をメールでシェアする

0 comments

コメントはまだありません。

コメントを追加する(不適切と思われるコメントは削除する場合があります)