php排列递归和排列组合实例代码详解
程序员文章站
2022-05-10 20:50:19
...
1. 排列递归
如果用P表示n个元素的全排列,而Pi表示n个元素中不包含元素i的全排列,(i)Pi表示在排列Pi前面加上前缀i的排列,那么n个元素的全排列可递归定义为:
① 如果n=1,则排列P只有一个元素i;
② 如果n>1,则全排列P由排列(i)Pi构成;
根据定义,可以看出如果已经生成(k-1)个元素的排列Pi,那么k个元素的排列可以在每个Pi前面加上元素i而生成。
代码:
function rank($base, $temp=null) { $len = strlen($base); if($len <= 1) { echo $temp.$base.'<br/>'; } else { for($i=0; $i< $len; ++$i) { rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]); } } } rank('123');
不过,经多次测试运行结果,发现存在一个问题:若是存在相同的元素,则全排列有重复。
例如'122'的全排列只有三种情况:'122'、'212'、'221';上面方法却有重复。
略修改,加个判断重复的标志,解决了问题(代码如下):
function fsRank($base, $temp=null) { static $ret = array(); $len = strlen($base); if($len <= 1) { //echo $temp.$base.'<br/>'; $ret[] = $temp.$base; } else { for($i=0; $i< $len; ++$i) { $had_flag = false; for($j=0; $j<$i; ++$j) { if($base[$i] == $base[$j]) { $had_flag = true; break; } } if($had_flag) { continue; } fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]); } } return $ret; } print '<pre>'; print_r(fsRank('122')); print '</pre>';
2. 排列组合实例
<?php /** * 要解决的数学问题 :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, * 由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 */ /* ################################### 开始计算 ################################### */ /** * 需要进行排列组合的数组 * * 数组说明:该数组是一个二维数组,第一维索引代表班级编号,第二维索引代表学生编号 */ $CombinList = array(1 => array("Student10", "Student11"), 2 => array("Student20", "Student21", "Student22"), 3 => array("Student30"), 4 => array("Student40", "Student41", "Student42", "Student43")); /* 计算C(a,1) * C(b, 1) * ... * C(n, 1)的值 */ $CombineCount = 1; foreach($CombinList as $Key => $Value) { $CombineCount *= count($Value); } $RepeatTime = $CombineCount; foreach($CombinList as $ClassNo => $StudentList) { // $StudentList中的元素在拆分成组合后纵向出现的最大重复次数 $RepeatTime = $RepeatTime / count($StudentList); $StartPosition = 1; // 开始对每个班级的学生进行循环 foreach($StudentList as $Student) { $TempStartPosition = $StartPosition; $SpaceCount = $CombineCount / count($StudentList) / $RepeatTime; for($J = 1; $J <= $SpaceCount; $J ++) { for($I = 0; $I < $RepeatTime; $I ++) { $Result[$TempStartPosition + $I][$ClassNo] = $Student; } $TempStartPosition += $RepeatTime * count($StudentList); } $StartPosition += $RepeatTime; } } /* 打印结果 */ echo "<pre>"; print_r($Result); ?>
以上就是php排列递归和排列组合实例代码详解的详细内容,更多请关注其它相关文章!
上一篇: php解析xml文件的方法
下一篇: ios开发swift Lable标签