作者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