━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 チャレンジ問題 (集合の分割の列挙)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●報告内容

以下の問題への答案のファイル(プログラムファイルと報告ファイル)を作り，
1月12日(金)の10:30までに Moodle で提出する．
答案の内容に応じて，最大で期末試験10点分の加点評価がなされる．
プログラムや実行結果が単に羅列されたものより，丁寧な解説や考察のあるものが
高く評価される．

●問題

(1) 入力として非負整数 n が与えられたときに，集合 {1,…,n} を
非空部分集合の族へと分割する方法すべてを，重複なく列挙するプログラムを作れ．
入力はコマンドライン引き数から受け取り，結果は標準出力に書き出すこと．
たとえば入力 n＝4 に対して，次の15個の集合族を出力できればよい．
----------------------------------------------------------------------
{{1,2,3,4}}
{{1,2,3},{4}}
{{1,2,4},{3}}
{{1,2},{3,4}}
{{1,2},{3},{4}}
{{1,3,4},{2}}
{{1,3},{2,4}}
{{1,3},{2},{4}}
{{1,4},{2,3}}
{{1},{2,3,4}}
{{1},{2,3},{4}}
{{1,4},{2},{3}}
{{1},{2,4},{3}}
{{1},{2},{3,4}}
{{1},{2},{3},{4}}
----------------------------------------------------------------------
すべての分割が重複なく列挙できれば，出力はこの通りでなくてもよい．

(2) 作成したプログラムのアルゴリズムとその動作を，小さな n (3〜5程度)の
実行結果を使って解説せよ．

(3) 講義で学んだ(あるいは独学した)データ構造やアルゴリズム設計技法が，
作成したプログラムでどのように使われているかを，使用理由と共に述べよ．

(4) 作成したプログラムの時間計算量について考察し，小さな n (0〜12程度) に
ついての実行時間に基づいて n＝15 の場合の実行時間を推測または実測せよ．
計算量の解析が難しいなら，分割の総数の変化に基づいて考察してもよい．

(5) 余力があれば，データ構造やアルゴリズムを変えたプログラムを作り，
実行時間や記憶量の観点での得失を論じよ．

●提出要領

問題(1)の答案は partitions.c (拡張子は適宜変更，他のファイルも必要なら追加)
というプログラムファイルに書き，問題(2)〜(5)の答案は report.pdf という
報告ファイルに書く．各ファイルの冒頭には学籍番号と氏名を書くこと．

プログラミング言語には paiza.IO 上で動作するものを使える．
プログラムには，適度に注釈を入れて読みやすくする．また，報告でプログラムや
実行結果を引用して説明する際には，どの部分の説明か分かりやすいように，
行番号や記号等の目印を付ける．

基礎知識の文献調査や，他人との意見交換を推奨するが，プログラムや報告は
自らの理解に基づいて自作する．他人の文書(または生成AI等の出力)を
参考にした場合には，ファイル中に出典(本の情報やウェブページのアドレス等)を
明示すること．また，他人と相談して答案を作った場合にも，
誰とどの部分について相談し，自分で考えた(作った)部分がどこかを明記すること．
出典を示さずに他人の文書等を転載(流用)した報告は，0点と評価される．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/