PHP排列组合及性能对比

2014-11-25 liyangweb.com 李杨 PHP

需求是这样的:

找到数组中所有可能的指定长度的组合,要求没有重复。

我从网上找了几个比较靠谱的算法,这里对比一下。。。

方法一:

function getCombinationToString($arr,$m){
    $result = array();
    if ($m ==1){
       return $arr;
    }
    
    if ($m == count($arr)){
        $result[] = implode(',' , $arr);
        return $result;
    }
        
    $temp_firstelement = $arr[0];
    unset($arr[0]);
    $arr = array_values($arr);
    $temp_list1 = getCombinationToString($arr, ($m-1));
    
    foreach ($temp_list1 as $s){
        $s = $temp_firstelement.','.$s;
        $result[] = $s;
    }
    unset($temp_list1);

    $temp_list2 = getCombinationToString($arr, $m);
    foreach ($temp_list2 as $s){
        $result[] = $s;
    }    
    unset($temp_list2);
    
    return $result;
}
$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18);
$t = getCombinationToString($arr, 6);

var_dump($t);

执行时间:238ms。

方法二:

function getCombinAryByNum( $arr, $num,$t=array()) {
  if ($num == 0) {
    return array($t);
  }
  $r = array();
  for ($i=0,$l=count($arr); $i <= $l-$num; $i++) {
    $tmp = getCombinAryByNum( array_slice($arr, $i+1, $l, false), $num-1,array_merge($t, array($arr[$i])));
    $r = array_merge($r, $tmp);
  }
  return $r;
}

$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18);
$numum = 6;
$ss = getCombinAryByNum($arr,$numum);

var_dump($ss);

执行时间:710ms。

 

可见方法一更优,速度大概是方法二的三倍。

标签: PHP 排列组合

发表评论:

Powered by emlog 冀ICP备13011830号-1