作者tropical72 (藍影)
站內Prob_Solve
標題[問題] 窮舉所有分組可能
時間Wed Aug 10 15:33:25 2011
各位先進好,
目前我遇到一些問題, 卡了二、三天仍一點頭緒都沒有,
試著轉換後之敘述大致如下
-----
[問題敘述]
假設一班有 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
1F：→ suhorng:枚舉所有可能,還是要計算個數? 08/10 15:53
2F：→ tropical72:是要枚舉出來，原問題是要針對各組別(集合)做處理. 08/10 15:54
3F：→ tropical72:當然若願順帶告訴小弟，這問題複雜度「頗高」，小弟將 08/10 15:55
4F：→ tropical72:視複雜度進行 S 與 N 之調整 (以致不會跑太久) XD 08/10 15:56
5F：→ suhorng:如果限制每一組編號最小的學生的編號要遞增呢 ? 08/10 16:10
6F：→ tropical72:抱歉,有點不懂s大之意.若問編號是否為連續,是的(編號 08/10 16:20
7F：→ tropical72:自定),但要串遍的話,該如何限制、確認每組最小編號 ? 08/10 16:20
8F：→ suhorng:喔,編號要連續 ? 那限制一下每一組的學生編號 都要比下一 08/10 16:21
9F：→ suhorng:組的學生編號還小試試看 ? 08/10 16:22
10F：→ suhorng:就是 直接把 1...N 分成 M 段, 第一段就第一組, 第二段就 08/10 16:25
11F：→ suhorng:第二組...這樣有符合你要求嗎 ?08/10 16:25
耶.. 抱歉我語意讓您誤會了, S1, S3 | S2, S4 | S5~S9
這是可以的。分組時編號可以不用連續。 (補齊)
※ 編輯: tropical72 來自: 180.177.78.41 (08/10 16:27)
12F：推 suhorng:嗯 那每組都有個編號最小的學生 限制第一組編號最小的學生 08/10 16:27
13F：→ suhorng:< 第二組編號最小的學生 < 第三組編號最小的學生... ? 08/10 16:28
15F：→ tropical72:!! 太神了, 我研究一下程式碼, 真是感謝 !! 08/10 16:30
16F：→ tropical72:我想問一下,這就只用到dfs,沒有其它再艱澀演算演在裡面 08/10 16:34
17F：→ tropical72:了嗎 ? ( 搞了三天竟死在 dfs... Orz.. ) 08/10 16:34
18F：→ firejox:理論上是只有dfs而已... 08/10 16:35
19F：→ suhorng:也許不算DFS...枚舉而已 符合那個條件 應該就不會重複了@@ 08/10 16:35
20F：→ tropical72:抱歉數學不好,我想再請教一下,在已知 N,M 情況下,它的 08/10 16:36
21F：→ tropical72:解答數是否可如何表達？ 08/10 16:37
22F：→ suhorng:印象中是第二類Stirling數... 08/10 16:40
23F：→ tropical72:謝謝 suhorng 大指教,我找到說明與公式了,感激不盡！ 08/10 16:42
24F：→ tkcn:題目不會發生 M = N 的情況嗎? 08/10 17:57
25F：→ suhorng:應該不是很重要 ? 08/10 19:38
26F：→ tropical72:在我所研究的議題裡，實際上 M << N 08/10 21:19