# 集合の分割の列挙
# データ構造・アルゴリズム論 チャレンジ問題 山田俊行 (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)