1. 順列再帰
P が n 個の要素の完全な配列を表し、Pi が要素 i を含まない n 個の要素の配列全体を表す場合、 (i) Pi は配列 Pi の前に接頭辞 i を付けた配列を表します。 、 n 個の要素の合計配置は次のように再帰的に定義できます。
① n=1 の場合、配置 P には要素 i が 1 つだけあります。
② n>1 の場合、全体の配置 P は配置 (i)Pi で構成されます。 ;
定義によれば、(k-1) 個の要素の配列 Pi が生成されている場合、各 Pi の前に要素 i を追加することで k 個の要素の配列を生成できることがわかります。
コード:
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」の 3 つの状況しかありませんが、上記の方法が繰り返されます。
少し変更し、重複を判断するためのフラグを追加し、問題を解決しました (コードは次のとおりです):
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 class="brush:php;toolbar:false">'; print_r(fsRank('122')); print '';
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 class="brush:php;toolbar:false">"; print_r($Result); ?>
以上がPHPの順列再帰と順列と組み合わせのコード例を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。