学步园

今天拿出我那本几年前买的冶工版的算法书翻了半天.组合算法那章发现只讲了排列算法和幂集算法

(这类问题的解法基本没下过功夫,临时拿来补一下).囧...那这章为啥要叫"组合问题算法"?

最后自己按照类似书上所写排列算法的decrease-by-one的思路弄出了一个.思路如图:

假设有集合A的元素包含0 1 2 3,在其中任取3个不重复的元素组成一个组合

则可表示为这样三棵树:

对应组合:

013

012

023

123

其中每个由根结点到其叶子节点的路径所经过的节点即是一个组合.第三棵树由于找不

到所需的节点而终止.树的问题很容易可以转换成一个递归解决.文字描述啥的俺不太擅

长,直接上代码:

function print (m){<br /> WScript.Echo (m);<br /> }<br /> //求排列数<br /> function a (n,m){<br /> if (m == 0)<br /> return 1;<br /> if (m>n)<br /> return 0;<br /> var ret = n;<br /> for (var i =1;i<=(m-1);++i){<br /> ret*=n-i;<br /> }<br /> return ret;<br /> }<br /> //组合数<br /> function c (n,m){<br /> return a(n,m)/a(m,m);<br /> }</p> <p>//求全排列<br /> function permutation (n,handler){<br /> }<br /> //求重复排列<br /> function permutation2 (n,handler){<br /> }<br /> //求组合<br /> function cb (si,s,n,m,r,h){<br /> r[si]=s;//填充位,<br /> if (si == m-1)//填充满了,调用回调函数<br /> {<br /> h (r);<br /> return;<br /> }<br /> ++si;<br /> for (s=++s;s<n;++s){<br /> cb (si,s,n,m,r,h);//递归填充下一位<br /> }<br /> }<br /> //求组合<br /> function combination (n,m,handler){<br /> if (m>n)<br /> return;</p> <p> var result = new Array();</p> <p> for (var i = 0;i<n-m+1;++i)<br /> cb (0,i,n,m,result,handler);<br /> }</p> <p>var nn = 4;<br /> var mm = 3;<br /> print ("总共" + c (nn,mm) + "种组合:");<br /> combination (nn,mm,function (r){<br /> var str = "";<br /> for (var i = 0;i<r.length;++i){<br /> str += r[i]+" ";<br /> }<br /> print (str);<br /> });

使用cscript运行后输出:

总共4种组合:
0 1 2
0 1 3
0 2 3
1 2 3