# 集合の分割の列挙 # データ構造・アルゴリズム論 チャレンジ問題 山田俊行 (2023.1.12) # 実行方法: python3 partitions.py [数] def partitions(seq): """列表現された集合の分割を再帰的に列挙""" if len(seq) == 0: return [[]] front, last = seq[:-1], seq[-1:] return [new_seq for p in partitions(front) for new_seq in expand(p, last)] def expand(p, last): """要素を一つ加えて分割を拡張""" return [p[:i] + [p[i]+last] + p[i+1:] for i in range(len(p))] + [p+[last]] def print_partition(p): """分割を表示""" print(repr(p).replace(" ","").replace("[","{").replace("]","}")) if __name__ == "__main__": import sys size = int(sys.argv[1]) if len(sys.argv) > 1 else 4 elements = list(range(1, size+1)) for p in partitions(elements): print_partition(p)