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

lvyehuaigu · 发表于 2006-6-11 18:16

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

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

风花雪月 · 发表于 2006-6-15 20:32

<DIV class=quote>以下是引用lvyehuaigu在2006-6-11 18:16:28的发言： 这也就是说，C(n,m)个组合其实已经和自然数集合{1，2，3，......，C(n,m)}建立了一一对应，但是如果我们想要C(n,m)个组合中的其中第k个组合C1C2C3...Cm,按照这个递推算法就必须求出前k-1个组合，显然随着k的增大，所需的时间损耗是巨大的，甚至规模比较大时，这不是一个可行的算法。 我想问的就是有没有这样的一种算法，当我们已知自然数0<k<C(n,m),可以很快的（不必去计算前k-1个组合）按照上边的那种组合排序规则求出第k个组合具体是什么？甚至反过来，当我给定一个组合，马上能返回一个对应的自然数k，表示这是第k个组合？ </DIV>
不需要这么麻烦的，你可以直接找到组合和k的对应关系 由于比较忙，暂时没功夫给把具体的规律找出来就按照你上面的例子简单叙述一下，规律你自己总结吧 第一个值第二个值组合数 1 2 4组 1 3 3组 1 4 2组 1 5 1组 2 3 3组 2 4 2组 2 5 1组 3 4 2组 3 5 1组 4 5 1组

账号		自动登录	找回密码
密码			我要加入

[经典算法] 关于组合生成的算法的讨论及疑问？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（lvyehuaigu）关于组合生成的算法的讨论及疑问...

浏览过的版块