组合数公式是指从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合,从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数,用符号c(n,m) 表示,下面我们来看用php来实现.

一、公式,有时候也表示成:

c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)

二、性质

c(n,m)=c(n,n-m);

三、递推公式

c(n,m)=c(n-1,m-1)+c(n-1,m)

等式左边表示从n个元素中选取m个元素,而等式右边表示这一个过程的另一种实现方法:任意选择n中的某个备选元素为特殊元素,从n中选m个元素可以由此特殊元素的分成两类情况,即m个被选择元素包含了特殊元素和m个被选择元素不包含该特殊元素,代码如下:

1. <?php 
2. //实现数学上的组合数算法 
3. header("content-type:text/html;charset=utf-8"); 
4. /** 
5.  * 在数组$a中任意m个元素组合 
6.  * 
7.  * @param array $a 候选的集合 
8.  * @param int $n 候选的集合大小 
9.  * @param int $m 组合元素大小 
10.  * @param array $b 储存当前组合中的元素，这里储存的是元素键值 
11.  * @param int $M 相当一个常量，一直保持不变 
12.  * @return */ 
13. function combine($a,$n,$m,$b,$M){ 
14.  for($i=$n;$i>=$m;$i--){ 
15.   $b[$m-1]=$i-1; 
16.   if($m > 1){ 
17.    $combine[]=combine($a,$i-1,$m-1,$b,$M); 
18.   }else{ 
19.    $onecombine=''; 
20.    for($j=$M-1;$j>=0;$j--){ 
21.     $onecombine.=$a[$b[$j]]; 
22.    } 
23.    $combine[]=$onecombine; 
24.    $onecombine=''; 
25.   } 
26.  } 
27.  return $combine; 
28. } 
29. /** 
30.  * 递归输出数组 
31.  * 
32.  * @param array $arr 待输出的数组 
33.  * @return int 返回数组元素个数*/ 
34. function recursionarray($arr){ 
35.  $i=0; 
36.  foreach($arr as $value){ 
37.   if(is_array($value)){ 
38.    $i+=recursionarray($value); 
39.   }else{ 
40.    echo $value."<br/>"; 
41.    $i++; 
42.   }  //开源软件:phpfensi.com 
43.  } 
44.  return $i; 
45. } 
46. $a=array('A','B','C','D','E','F','G','H','I','J'); 
47. $b=array(); 
48. $combine=combine($a,10,5,$b,5); 
49. $count=recursionarray($combine); 
50. echo "总共有".$count."组合"; 
51. ?>

Tags: PHP组合算法 PHP数学算法

分享到：