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

lvyehuaigu

昨天有朋友问起组合的生成算法，于是就翻了翻组合数学的书，总结一下书上的组合生成算法：
现在以从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个组合？

[ 本帖最后由 lvyehuaigu 于 2006-6-11 18:31 编辑 ]

desert007

楼主，你解决你的最后提出的问题了没。我也碰到这样个问题了，希望给点指教。

liuyalong008

desert007 发表于 2013-6-15 18:56
楼主，你解决你的最后提出的问题了没。我也碰到这样个问题了，希望给点指教。 ...

最近本论坛此问题讨论了多次了
http://forum.simwe.com/thread-1080238-1-2.html
http://forum.simwe.com/thread-1079234-1-2.html

1. >> a=nchoosek(1:6,3)
   
2. 
   
3. a =
   
4. 
   
5.      1     2     3
   
6.      1     2     4
   
7.      1     2     5
   
8.      1     2     6
   
9.      1     3     4
   
10.      1     3     5
    
11.      1     3     6
    
12.      1     4     5
    
13.      1     4     6
    
14.      1     5     6
    
15.      2     3     4
    
16.      2     3     5
    
17.      2     3     6
    
18.      2     4     5
    
19.      2     4     6
    
20.      2     5     6
    
21.      3     4     5
    
22.      3     4     6
    
23.      3     5     6
    
24.      4     5     6

复制代码

desert007

liuyalong008 发表于 2013-6-15 20:20
最近本论坛此问题讨论了多次了
http://forum.simwe.com/thread-1080238-1-2.html
http://forum.simwe.com/ ...

有没有fortran的？matlab，mathematica里实现这个是很方便，因为软件已经把函数内置了。不过我想的是有没有fortran的，因为一般来说这个速度要比前两个快

liuyalong008

desert007 发表于 2013-6-17 05:40
有没有fortran的？matlab，mathematica里实现这个是很方便，因为软件已经把函数内置了。不过我想的是有没 ...

fortran的速度是领略过了，你可以open nchoosek，然后把它的代码转成fortran，基本都是基础代码，应该难度不大，但是会很耗时间