php实现排列组合
一、总结
1、回溯：回溯的函数参数有些生疏了，记录递归的位置（pos或step），还要有东西（vis数组）来记录这个是否已经被访问
2、php全局变量的使用 ：外部定义的普通变量，函数内部定义global
二、代码
需求：php实现排列组合
代码一：
/**
* 排列组合
* 采用二进制方法进行组合的选择，如表示5选3时，只需有3位为1就可以了，所以可得到的组合是 01101 11100 00111 10011 01110等10种组合
*
* @param 需要排列的数组 $arr
* @param 最小个数 $min_size
* @return 满足条件的新数组组合
*/
function pl($arr,$size=5) {
$len = count($arr);
$max = pow(2,$len);
$min = pow(2,$size)-1;
$r_arr = array();
for ($i=$min; $i<$max; $i++){
$count = 0;
$t_arr = array();
for ($j=0; $j<$len; $j++){
$a = pow(2, $j);
$t = $i&$a;
if($t == $a){
$t_arr[] = $arr[$j];
$count++;
}
}
if($count == $size){
$r_arr[] = $t_arr;
}
}
return $r_arr;
}
$pl = pl(array(1,2,3,4,5,6,7),5);
var_dump($pl);
代码二：
<?php
namespace app\index\controller; use app\index\controller\Base; class Exercise extends Base
{
public function index()
{
// return view('insert_array');
$this->plzhDemo();
} /**
* php实现排列组合
* 参数：传入数组 排列组合所取的位数 vis数组 ans数据用来记录每次的结果
* 算法；递归（回溯）
* 返回值：返回排列组合结果数组
* @return [type] [description]
*/
private $count1=0;
public function plzh($arr,$n,$pos,$vis,$ans){
//1、递归返回条件：位数够了就可以返回了
if($pos>$n-1){
global $count1;
$count1++;
dump($ans);
}else{
$len=count($arr);
for ($i=0; $i < $len; $i++) {
if($vis[$i]==0){//没取
$ans[$pos]=$arr[$i];
$vis[$i]=1;
$this->plzh($arr,$n,$pos+1,$vis,$ans);
$vis[$i]=0;
}
}
}
//2、递归里面的算法（一位一位的来取）取一位之后，把这一位的数标记置为已经取了，然后取后面的位的时候从没有取的数里面取，所以需要标记数组
//2.1、 从未取的数里面依次取一位就好 }
public function plzhDemo(){
$arr=array(1,2,3,4,5,6,7);
$n=5;
$vis=array();
for ($i=0; $i <=count($arr) ; $i++) {
$vis[$i]=0;
}
$ans=array();
$this->plzh($arr,$n,0,$vis,$ans);
global $count1;
dump($count1);
} }
截图：