PHP 从m个数中任取n个数的排列组合算法

从m个数中任取n个数的排列组合算法!

$n = array(1,2,3,4,5,6,7,8,9,10);
//$n = array(1,2,3,4);
/**
$n 数据数组
$m 组合串的长度
$s 用于缓存中间量
**/
function permutation($n, $m = 0, $s = ''){
static $results = array();

if($m == 0) {
$results[] = substr($s,1);//如果长度够了则赋值
}else {
for($i=0; $i < count($n); $i++) {
//echo "==$i===>".$s."\n";
permutation($n, $m-1, $s.','.$n[$i]);
}
}
return $results;
}

$t1 = microtime(true);
$rst = permutation($n, 2);
echo microtime(true) - $t1 ."\n";
//print_r($rst);

//////////////////
function combination($params){
foreach($params as $key => $val) {
$tmpArr = explode(',', $val);
if( 1 == count(array_unique($tmpArr))) {
continue;
}
sort($tmpArr);
$results[] = implode(',', $tmpArr);
}
$results = array_unique($results);

return $results;
}

$s = combination($rst);

print_r($s);
//exit;
function getCombinationCount($n, $k) {
//fscanf(STDIN,"%d,%d",$n,$k);
$r = 1;
while($k) $r *= $n--/$k--;
return $r;
}

echo count($s) . "===========" . getCombinationCount(10, 2);


exit;


加添一个快上N倍的算法：

var_dump(c(range(1,5), 2));

function c($ar,$n){
$c = count($ar);
if ($n>$c) return false; // parameter wrong
if ($c>50) return false; // too big array :)

$r = array();

$code = "";
$list = array();
for($i=1;$i<=$n;$i++){
$list[] = '$v'.$i;
$code .= 'foreach($ar as $k'.$i.'=>$v'.$i.'){';
if($i!=$n) $code .= 'unset($ar[$k'.$i.']);';
}
$code .= '$t = array('.join(',',$list).');';
$code .= 'sort($t);';
$code .= '$r[] = join(",",$t);';
for($i=$n-1;$i>0;$i--){
$code .= '}$ar[$k'.$i.']=$v'.$i.';';
}
$code .= '}';
/*
foreach($ar as $k1=>$v1){
unset($ar[$k1]);
foreach($ar as $k2=>$v2){
unset($ar[$k2]);
foreach($ar as $k3=>$v3){
$t = array($v1,$v2,$v3);
sort($t);
$r[] = join(',',$t);
}
$ar[$k2] = $v2;
}
$ar[$k1] = $v1;
}
*/
eval($code);
return array_values(array_unique($r));
}


再提供一下比快 N倍更快十倍的方法：
function array_combination(array $elements, $chosen)
{
$result = array();

for ($i = 0; $i < $chosen; $i++) { $vecm[$i] = $i; }
for ($i = 0; $i < $chosen-1; $i++) { $vecb[$i] = $i; }
$vecb[$chosen - 1] = count($elements) - 1;
$result[] = $vecm;

$mark = $chosen - 1;
while (true) {
if ($mark == 0) {
$vecm[0]++;
$result[] = $vecm;
if ($vecm[0] == $vecb[0]) {
for ($i = 1; $i < $chosen; $i++) {
if ($vecm[$i] < $vecb[$i]) {
$mark = $i;
break;
}
}
if (($i == $chosen) && ($vecm[$chosen - 1] == $vecb[$chosen - 1])) { break; }
}
} else {
$vecm[$mark]++;
$mark--;
for ($i = 0; $i <= $mark; $i++) {
$vecb[$i] = $vecm[$i] = $i;
}
$vecb[$mark] = $vecm[$mark + 1] - 1;
$result[] = $vecm;
}
}

return $result;
}


ini_set('memory_limit', '328M');
$n = 640 ; $m =2; $elements = range(1, $n);
$begin = microtime(TRUE);
$result = array_combination($elements, $m);
$end = microtime(TRUE);
echo "count: ".count($result) . PHP_EOL;
echo "time: ". 1000*($end-$begin) . " ms" . PHP_EOL;

echo '

';
//print_r($result);
echo '

';

/* output result
foreach($result as $indexes) {
foreach ($indexes as $index) {
echo $elements[$index] . "\t";
}

echo PHP_EOL;
}

*/