产生可重复组合的算法

win_hate

上次讨论了如何生成 n 个元素的 r 组合，那种组合中，元素是不可重复的。这次讨论可重复的组合。

一、在原来算法的基础上改

实际上对生成不可重复组合方法的分析，几乎可以原封不动地搬过来。差别在与对元素大小的估计。假定 n 个元素为 a_1 < a_2 <...<a_n, 在不可重复的组合中，一个组合 c_1 < c_2 < ...< c_r 中

设 c_i = a_l，由于 c_i 后还有 c_{i+1}, ..., c_{r} 共 r-i 个元素，这些元素要从 a_{l+1}...a_n 中选取，所以有

r-i <= n-l ==> l <= n-r+i ==>  c_{i-1} < c_i <= a_{n-r+i}

但对与可重复的排列而言，若 c_{i-1} = a_l，则 c_i 可取  a_l, ..., a_n， 即上限变为 a_n

所以把生成组合的方法略作修改，就可以得到生成可重复组合的算法，即最小组合为 a_1,..., a_1，最大组合为 a_n, ..., a_n，从一个组合得到下一个组合的方式为：

从右向左少描，找到第一个比 a_n 小的 c_i，

若找到了，则把 c_i 增大 1，把 c_{i+1},...,c_{r} 的值设为 c_i.

若找不到这样的 c_i 则表明已经是 a_n,..., a_n，没有下一组合了。


代码我就不写了，跟不重复的差不多。举一个例子：4 的可重复 3 组合

111
112
113
114
-----------------
122      c_2+=1, c_3 <- c_2
123
124
-----------------
133      c_2+=1, c_3 <- c_2
134
144
-----------------
222      c_1+=1, {c_2, c_3} <- c_1
223
224
233
234
244
-----------------
333      c_1+=1, {c_2, c_3} <- c_1
334
344
444


二、直接使用原来的算法

n 元素的 r 可重复组合个数为  binomial (n+r-1, r)，恰好是 n+r-1 元素的 r 组合个数。这提醒我们，可重复组合和不可重复组合间有某种联系。事实上，若你能自行计算出 n 元素的 r 可重复组合个数为  binomial (n+r-1, r)，则算法是十分明显的。

设 n 元素 a_1<a_2<...< a_n 的 r 可重复组组合的集合为 DC，在 a_1 ... a_n  后添加 r-1 个元素 a_{n+1}, ..., a_{n+r-1}， 使得 a_1 < a_2 <...< a_{n+r-1} 设 n+r-1 的 r 不可重复组合集为 C。

f 为一个 DC -> C 的映射，若 X = (c_1, ..., c_r) in DC, 设 c_i = a_j，则 c_i 被映射为

c_i = a_{j+i-1}。用普通语言描述就是 c_1 不动， c_2 增大 1，c_3 增大 2,..., c_r 增大 r-1.

g 为一个 C -> DC 的映射，若 X = (c_1, ...., c_r) in C, 设 c_i = a_j，则 c_i 被映射为 c_i = a_{j-i+1}. 即 c_1 不动，c_2 减少 1， c_3 减少 2, ..., c_r 减少 r-1。

容易验证 gf 是 DC 到自身的单位映射， fg 是 C 到自身的单位映射。所以 f 是 DC 到 C 的双射。

要得到 DC 只需要求出 C 并用 g 作用一下就好了。

也即

求出 a_1, ..., a_{n+r-1} 的 r 组合，然后把 a_2 调小 1， a_3 调小 2,..., a_{r} 调小 r-1, 就好了。前者可以用以前的代码直接生成。

这个方法比第一个慢一些，但从数学上看，很简洁。


相关连接：

生成组合的算法
http://bbs.chinaunix.net/redirec ... o=lastpost#lastpost

Blog 对应帖子：
http://www.cublog.cn/u/20/?u=htt ... howart.php?id=78756

[ 本帖最后由 win_hate 于 2006-2-26 20:06 编辑 ]