关于组合生成的算法的讨论及疑问？
<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<n-r+j的最大下标i。即i=max{j|cj<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)>=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<k<C(n,m),可以很快的（不必去计算前k-1个组合）按照上边的那种组合排序规则求出第k个组合具体是什么？甚至反过来，当我给定一个组合，马上能返回一个对应的自然数k，表示这是第k个组合？
页:
[1]