php通过排列组合实现1到9数字相加都等于20的方法
本文实例讲述了php通过排列组合实现1到9数字相加都等于20的方法。分享给大家供大家参考。具体实现方法如下：
<?php
set_time_limit(0);
/*
函数说明：huoqu_zhuhe($eq,$jiashu,$isone=0)
参数说明：$eq---几个数相加的总和；
$jiashu-------加数数组：$jiashu=array(1,2,3,4,5,6,7,8,9)，可以使用的加数；
$isone---是否要每次使用不同的加数，唯一性，1是0不，默认1
返回类型:数组，数字以+相连的字符串：[0]=>3+8+9[1]=>4+7+9
测试效果：1：对于加数数组比较小的，速度可以，过大的话，有些慢；2：每次可以使用不同的加数的，处理会变慢
采用的方法是：生成所有可能排列，对排列处理过滤重复的，得到组合
*/
functionhuoqu_zhuhe($eq,$jiashu,$isone=1)
{if(empty($jiashu)||!is_array($jiashu)){echo'error:加数必须数组';returnfalse;}
$feishu=0;
for($i=0;$i<count($jiashu);$i++){
if(!is_numeric($jiashu[$i])){$feishu=1;break;}
}
if($feishu==1){echo'error；数组中必须是合法的数字';returnfalse;}
$lian=$jiashu;
$savearr=array();
while(!empty($lian)){
//echo1;
$newarr=array();
$k=0;
for($i=0;$i<count($lian);$i++){
$lianstr=$lian[$i];
$arr=explode('+',$lianstr);
$nowhe=array_sum($arr);
//echo$nowhe;
for($j=0;$j<count($jiashu);$j++){
$savestr=$lianstr.'+'.$jiashu[$j];
if($isone==1&&in_array($jiashu[$j],$arr))continue;
if(($nowhe+$jiashu[$j])>$eq)break;
elseif(($nowhe+$jiashu[$j])==$eq){
$savearr[]=$savestr;
}
else{$newarr[$k]=$savestr;$k++;}
}//endfor($j=0;$j<count($jiashu)
}//endfor($i=0;$i
$lian=$newarr;
}//endwhile(!empty($lian))
//print_r($savearr);
//生成组合部分，过滤重复，2个数组以一个为参考，看另一个是否能通过移动达到匹配，可以，过滤
$isguolu=array();//存储对应的id的取舍0取1舍
for($i=0;$i<count($savearr);$i++){
$isguolu[]=0;
}//初始化全部0
for($i=0;$i<count($savearr);$i++){
$arr1=explode('+',$savearr[$i]);
$len1=count($arr1);
for($j=$i+1;$j<count($savearr);$j++){
$arr2=explode('+',$savearr[$j]);
$len2=count($arr2);
if($len1!=$len2)continue;
if($isguolu[$j]==1)continue;
//比较$arr1和$arr2开始
$jishu=0;
for($i1=0;$i1<count($arr1);$i1++){
$a=$arr1[$i1];
$isyou=0;
for($i2=$i1;$i2<count($arr2);$i2++){
if($a==$arr2[$i2]){
$jishu++;
$isyou=1;
$t=$arr2[$i1];
$arr2[$i1]=$arr2[$i2];
$arr2[$i2]=$t;
break;
}
}//endfor($i2=0
if($isyou==0)break;
}//endfor($i1=0;$i1<count($arr1);
if($jishu==$len1)$isguolu[$j]=1;
}//endfor($j=$i+1;
}//endfor($i=0;$i<count($savearr);$i++)
//print_r($isguolu);
//根据过滤数组选择
$newarr=array();
for($i=0;$i<count($savearr);$i++){
if($isguolu[$i]==0)$newarr[]=$savearr[$i];
}
//print_r($newarr);
return$newarr;
}
//下面是一个测试
//取用1,2,3,4,5,6,7,8,9相加所有等于20的组合
$jiashu=array(1,2,3,4,5,6,7,8,9);
$eq=20;
if($jieguo=huoqu_zhuhe($eq,$jiashu,1))print_r($jieguo);
?>
运行结果如下：
Array ( [0]=>3+8+9 [1]=>4+7+9 [2]=>5+6+9 [3]=>5+7+8 [4]=>1+2+8+9 [5]=>1+3+7+9 [6]=>1+4+6+9 [7]=>1+4+7+8 [8]=>1+5+6+8 [9]=>2+3+6+9 [10]=>2+3+7+8 [11]=>2+4+5+9 [12]=>2+4+6+8 [13]=>2+5+6+7 [14]=>3+4+5+8 [15]=>3+4+6+7 [16]=>1+2+3+5+9 [17]=>1+2+3+6+8 [18]=>1+2+4+5+8 [19]=>1+2+4+6+7 [20]=>1+3+4+5+7 [21]=>2+3+4+5+6 )
希望本文所述对大家的php程序设计有所帮助。