组合算法PHP版




问题:在一个n个元素的集合中,取出r个元素,有多少种取法,并把不同取法结果输出

解法一(递归)

 function Combination($n , $r){
   $result = array();
   if ($r==1) {
     foreach ($n as $entry){
       $result[] = array($entry);
     }
   }else{
     foreach ($n as $k=>$entry){
       unset($n[$k]);
       $sub_combination = Combination($n, $r-1);
       foreach ($sub_combination as $entry_combination){
         $result[] = array_merge(array($entry),$entry_combination);
       }
     }
   }
   return $result;
 }
//测试
$n = array(1,2,3,4,5);
$result = Combination($n , 3);
var_export($result);
//输出
array (
  0 => 
  array (
    0 => 1,
    1 => 2,
    2 => 3,
  ),
  1 => 
  array (
    0 => 1,
    1 => 2,
    2 => 4,
  ),
  2 => 
  array (
    0 => 1,
    1 => 2,
    2 => 5,
  ),
  3 => 
  array (
    0 => 1,
    1 => 3,
    2 => 4,
  ),
  4 => 
  array (
    0 => 1,
    1 => 3,
    2 => 5,
  ),
  5 => 
  array (
    0 => 1,
    1 => 4,
    2 => 5,
  ),
  6 => 
  array (
    0 => 2,
    1 => 3,
    2 => 4,
  ),
  7 => 
  array (
    0 => 2,
    1 => 3,
    2 => 5,
  ),
  8 => 
  array (
    0 => 2,
    1 => 4,
    2 => 5,
  ),
  9 => 
  array (
    0 => 3,
    1 => 4,
    2 => 5,
  ),
)

 

解法二(非递归):

待续

相关数学知识:

排列及计算公式:

从n个不同元素中,任取m(m≤n)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号p(n,m)表示。

p(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(规定0!=1).

从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m)表示。

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

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

谢 懿茂
关于

IT浪潮瞬息万变,争做一名弄潮的程序员! QQ:2646739154

标签: ,

发表评论