[問題] 窮舉所有分組可能

[tropical72 (藍影)]

各位先進好,

目前我遇到一些問題, 卡了二、三天仍一點頭緒都沒有,

試著轉換後之敘述大致如下

-----

[問題敘述]

假設一班有 N 個學生 (S[1..N]) ，在一份報告中要分成 M (M < N) 組進行報告，
分組的規則為

(1) 每組人數至少 1 人
(2) 必為 M 組

假設 10 人分 3 組， S1~S3 | S4~S5 | S6~S10 ，
與                  S4~S5 | S1~S3 | S6~S10   視為同一種分類

(成員都一樣，只是畫分的組別不一樣而已，視為同一種分類)

試問該如何串遍 (列舉) 所有的可能分組？

-----

這次很遺憾卡了三天, 一點想法、靈感都找不到 Orz

請問是否有建議的方式，或已有較佳效率之演算法可達成我的目的？

謝謝各位不吝指教，小弟感激不盡！

--
YouLoveMe() ? LetItBe() : LetMeFree();

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
→ suhorng:枚舉所有可能,還是要計算個數?
→ tropical72:是要枚舉出來，原問題是要針對各組別(集合)做處理.
→ tropical72:當然若願順帶告訴小弟，這問題複雜度「頗高」，小弟將
→ tropical72:視複雜度進行 S 與 N 之調整 (以致不會跑太久) XD
→ suhorng:如果限制每一組編號最小的學生的編號要遞增呢 ?
→ tropical72:抱歉,有點不懂s大之意.若問編號是否為連續,是的(編號
→ tropical72:自定),但要串遍的話,該如何限制、確認每組最小編號 ?
→ suhorng:喔,編號要連續 ? 那限制一下每一組的學生編號 都要比下一
→ suhorng:組的學生編號還小試試看 ?
→ suhorng:就是 直接把 1...N 分成 M 段, 第一段就第一組, 第二段就
→ suhorng:第二組...這樣有符合你要求嗎 ?
耶.. 抱歉我語意讓您誤會了,  S1, S3 | S2, S4 | S5~S9
這是可以的。分組時編號可以不用連續。 (補齊)
※ 編輯: tropical72      來自: 180.177.78.41        (08/10 16:27)
推 suhorng:嗯 那每組都有個編號最小的學生 限制第一組編號最小的學生
→ suhorng:< 第二組編號最小的學生 < 第三組編號最小的學生... ?
→ suhorng:像這樣可以嗎 ? http://pastie.org/2349352
→ tropical72:!! 太神了, 我研究一下程式碼, 真是感謝 !!
→ tropical72:我想問一下,這就只用到dfs,沒有其它再艱澀演算演在裡面
→ tropical72:了嗎 ? ( 搞了三天竟死在 dfs... Orz.. )
→ firejox:理論上是只有dfs而已...
→ suhorng:也許不算DFS...枚舉而已 符合那個條件 應該就不會重複了@@
→ tropical72:抱歉數學不好,我想再請教一下,在已知 N,M 情況下,它的
→ tropical72:解答數是否可如何表達？
→ suhorng:印象中是第二類Stirling數...
→ tropical72:謝謝 suhorng 大指教,我找到說明與公式了,感激不盡！
→ tkcn:題目不會發生 M = N 的情況嗎?
→ suhorng:應該不是很重要 ?
→ tropical72:在我所研究的議題裡，實際上 M << N