2024/12/25

題目說明:

有一個課程有 n 位同學修課，同學編號為 0,1,2,...,n-1，學期中需要分組完成專案，每組最少一位同學，每位同學都需要參與，但是只能參與一組，請列印出所有可能的分組方法，如下面範例測資所示，輸出的時候請用兩種方式輸出，第一種運用限制增長字串 Restricted Growth String (RGS) 標示每一位同學組別，所謂的 RGS 字串 a₁, a₂, ..., a_n 是滿足 a₁=0, a_j+1 ≤ 1 + max(a₁, ..., a_j), 1≤j<n 的數字序列，例如 n=4 的時候，0 1 1 2 代表第一個同學的組別是 0，第二個同學的組別是 1，第三個同學的組別是 1，第四個同學的組別是 2，也就是說這個分組方式總共有 0,1,2 三組，組別 0 以集合 {0}₀ 表示，只包含編號 0 的同學，組別 1 以集合 {1, 2}₁ 表示，包含編號 1 和編號 2 的同學，組別 2 以集合 {3}₂ 只包含編號 3 的同學。

因為在課堂中需要逐一考量所有可能的分組方法，希望連續兩種分組方法之間只有一位同學的組別改變，組別只能以旋轉的方式改變 (0 -> 1 -> 2 -> 0)。例如：由分組方法 {0, 1, 3}₀, {2}₁ 改變為分組方法 {0, 3}₀, {1, 2}₁ 時，只有編號 1 的同學由第 0 組換到第 1 組，由分組方法 {0, 3}₀, {1, 2}₁ 改變為分組方法 {0}₀, {1,2,3}₁ 時，只有編號 3 的同學由第 0 組換到第 1 組，請撰寫程式依照上面的要求輸出所有可能的分組方法。

由於可能的分組方法實在太多，所以當 n 大於 10 的時候，只需要印出總共有多少種不同的分組方法即可。

輸入測試資料:

4↵

輸入只有一個整數 n，代表總共有 n 位同學修課，1≤n≤ 25。

輸出測試資料:

15↵
     1: 0 0 0 0    0 1 2 3↵
     2: 0 0 0 1    0 1 2 | 3↵
     3: 0 0 1 1    0 1 | 2 3↵
     4: 0 0 1 2    0 1 | 2 | 3↵
     5: 0 0 1 0    0 1 3 | 2↵
     6: 0 1 1 0    0 3 | 1 2↵
     7: 0 1 1 1    0 | 1 2 3↵
     8: 0 1 1 2    0 | 1 2 | 3↵
     9: 0 1 2 2    0 | 1 | 2 3↵
    10: 0 1 2 3    0 | 1 | 2 | 3↵
    11: 0 1 2 0    0 3 | 1 | 2↵
    12: 0 1 2 1    0 | 1 3 | 2↵
    13: 0 1 0 1    0 2 | 1 3↵
    14: 0 1 0 2    0 2 | 1 | 3↵
    15: 0 1 0 0    0 2 3 | 1↵

每一列輸出代表一種分組方法，冒號前是 6 位數的序號 (由 1 開始編號)，接下來是顯示每一位同學組別的 RGS 字串，組別由 0 開始編號，空 4 格以後列印各組成員，由第 0 組開始依序列印，每一組內同學的編號也由小到大依序列印，組別之間以 | 為分隔字元，每一同學編號以及 | 符號都以空格字元分隔。

提示：題目要求「連續兩種分組方法之間只有一位同學的組別改變」，可以用類似生成 GrayCode 的方法來改變 RGS 字串；集合不同的分割方法總數為 Bell Number，可以用一個遞歸公式 (recursion formula) 來描述。

1131 Final #2 [50%] 專案分組