作者tropical72 (蓝影)
站内Prob_Solve
标题[问题] 组合编码问题
时间Tue Jun 21 17:56:15 2011
数学没很好，希望可以给一点意见。
先假设有 5 个数要取 3 数做组合，共 5C3 = 10 种，
并「依序」做输出的话长这样
(1) 1 2 3 (2) 1 2 4 (3) 1 2 5 (4) 1 3 4 (5) 1 3 5
(6) 1 4 5 (7) 2 3 4 (8) 2 3 5 (9) 2 4 5 (10) 3 4 5
现我想要对它们做编码动作，若以编号 0 为第一组，
编号 0 : 1 2 3
编号 4 : 1 3 5
请问这样，有没有办法做
encode(组合对到编号) / decode(编号对到组合) 动作？
由於实际问题 mCn 结果还蛮大的，但我只需纪录其「该组合出现次数」即可，
所以想用这种方式节省记忆体空间，无奈便是 编解码 那里不知该如何下手，
请各位有经验之版友予以意见，
谢谢各位不吝指教。
--
YouLoveMe() ? LetItBe() : LetMeFree();
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.73.222
1F：→ suhorng:可以的, 但是计算过程会需要计算 mCn 之类... 如果 mCn 本 06/21 18:02
2F：→ suhorng:身就很大(超过long long之类,或算起来很慢)可能也不太方便 06/21 18:02
3F：→ suhorng:如果现在要对在 m 个数中取 n 个的组合进行编号, 那麽以 06/21 18:06
4F：→ suhorng:(由小到大)第 k 个数字开头的组合 编号自然在 06/21 18:06
5F：→ suhorng:C(n-1,m-1)+C(n-2,m-1)+...+C(n-k,m-1)和 06/21 18:12
6F：→ suhorng:C(n-1,m-1)+C(n-2,m-1)+...+C(n-k,m-1)+C(n-k+1,m-1)-1间, 06/21 18:12
7F：→ suhorng:所以在编解的时候可以一一枚举该位数字,顺便计算编号 06/21 18:13
8F：→ suhorng:有点类似康托展开,但是这次子问题的大小不是定值 06/21 18:14
9F：→ suhorng: ^^^^^^^^^^^打错了 多一项 06/21 18:15
抱歉一直插队, 现在补齐！该数学式确实没见过, 康托展开我也再去查查,
该数学式应是 (组合)--->(编号)，至此应可解决我的问题.
另一疑问是，是否有另一组类似 (编号)----> (组合)
※ 编辑: tropical72 来自: 180.177.73.222 (06/21 18:28)
10F：→ suhorng:反过来从编号求出组合也是一样的方法,就看编号位在哪一段 06/21 18:32
11F：→ suhorng:就知道现在应该要取剩下的第几大的数字 06/21 18:32