lvyehuaigu 发表于 2006-6-11 18:08

关于组合生成的算法的讨论及疑问?

<STRONG>关于组合生成的算法的讨论及疑问?<BR><BR></STRONG>昨天有朋友问起组合的生成算法,于是就翻了翻组合数学的书,总结一下书上的组合生成算法:<BR>现在以从1,2,3,4,5,6中取3个组合为例。<BR>(1)123、(2)124、(3)125、(4)126,(5)134、(6)135、(7)136,(8)145、(9)146,(10)234、(11)235......。<BR>       很容易从上边例子总结出规律,从而得到递推关系,如上例中的组合256,显然c2,c3已经分别达到5,6,故c1从2修改为3。c2,c3作相应的修改,分别改为4,5得345。即256的下一个组合应为345。<BR>    明白了以上的道理,归纳从一个组合c1c2...cr得到下一个组合的步骤如下:<BR>S1.求满足不等式cj&lt;n-r+j的最大下标i。即i=max{j|cj&lt;n-r+j}<BR>S2.ci=ci+1<BR>S3.cj=c(j-1)+1,j=i+1,i+2,...,r<BR>这样依照上述算法,就可以罗列出所有的从{1,2,3,.......,n}中取m个数的所有C(n,m)个组合,而且是按照上边那种顺序的。而且我写了个简单的matlab函数如下:<BR><FONT color=red>function zuhe(n,m)<BR>%组合生成算法。生成从1到n个数中选m个数的所有组合。<BR>%n----待选集个数。<BR>%m----组合个数。<BR>y=1:m;<BR>disp(y);<BR>while any(y~=n-m+1:n)<BR>%递推算法,返回下一个组合。<BR>    j=m;<BR>    while y(j)&gt;=n-m+j<BR>      j=j-1;<BR>    end<BR>    i=j;<BR>    y(i)=y(i)+1;<BR>    for j=i+1:m<BR>      y(j)=y(j-1)+1;<BR>    end<BR>    disp(y);<BR>end</FONT><BR>      这也就是说,C(n,m)个组合其实已经和自然数集合{1,2,3,......,C(n,m)}建立了一一对应,但是如果我们想要C(n,m)个组合中的其中第k个组合C1C2C3...Cm,按照这个递推算法就必须求出前k-1个组合,显然随着k的增大,所需的时间损耗是巨大的,甚至规模比较大时,这不是一个可行的算法。<BR>      我想问的就是有没有这样的一种算法,当我们已知自然数0&lt;k&lt;C(n,m),可以很快的(不必去计算前k-1个组合)按照上边的那种组合排序规则求出第k个组合具体是什么?甚至反过来,当我给定一个组合,马上能返回一个对应的自然数k,表示这是第k个组合?
页: [1]
查看完整版本: 关于组合生成的算法的讨论及疑问?