作者suhorng ( )
站内Prob_Solve
标题Re: [问题] 组合编码问题
时间Tue Jun 21 18:30:45 2011
假若要在 1, 2, 3, 4, 5 间选三个 编号
0 1 2 3 \
1 1 2 4 | 4
2 1 2 5 | C = 6
3 1 3 4 | 2
4 1 3 5 |
5 1 4 5 /
6+0 2 3 4 \ 3
6+1 2 3 5 | C = 3
6+2 2 4 5 / 2
2
6+3+0 3 4 5 | C = 1
2
大概是类似这种感觉, 跟我们对 n! 编号时类似, 但子集合的大小不再是固定的
//推文有些打错 抱歉
Encode (U,seq,len) // seq[0...len-1] 是待编码的组合(阵列)
if len = 1 then return 0
ret ← 0
kth ← 求出 seq[0] 是 U 由小到大第几大的数字 (1≦kth≦|U|)
for i = 1...kth-1
|U|-i
ret ← ret + C
len-1
return ret + Encode(U\{seq[0]}, seq+1, len-1)
n n-1 n-2 m n+1
而 C + C + C + ... + C = C
m m m m m+1
n n-1 n-2 n-k n+1 k
所以 C + C + C + ... + C = C - C
m m m m m m
//其实也不用这麽迂回...从第 k 大的数字往後数, 数量自然是 C(k,m) 个
※引述《tropical72 (蓝影)》之铭言：
: 数学没很好，希望可以给一点意见。
: 先假设有 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 结果还蛮大的，但我只需纪录其「该组合出现次数」即可，
: 所以想用这种方式节省记忆体空间，无奈便是 编解码 那里不知该如何下手，
: 请各位有经验之版友予以意见，
: 谢谢各位不吝指教。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.147.134
※ 编辑: suhorng 来自: 59.115.147.134 (06/21 18:34)
1F：推 tropical72:神之手出手相助了!! 大推 !! 非常感谢 !! 06/21 18:41
※ 编辑: suhorng 来自: 59.115.147.134 (06/21 18:44)
2F：→ firejox:推su大大 06/21 20:39