本篇程式有BUG,請改參考Permutations Generator (fixed) for PHP
因為上一篇文章排列組合公式函式只能算出組合的總數,所以最近趴文研究了一下,找到有一個現成的函式,不過似乎有點不足的地方,於是我重新修改了一下,增加可用性。目前這個版本是PHP,有時間我會再另發表一篇javascript的版本。還有...如果要拿去用的話>_<,通知一下吧,只是讓我知道這個程式有幫助到別人心裡也安慰點。另外,如果你想要的不是排列,而且是組合,那麼我之前也有寫一個排列組合 Combination for PHP的函式,可以參考看看。
//========================= // 使用方法 //========================= //從字串ABCD中任取3個字元排列,可重複選取 $result = permutations('ABCD',3,false); //從字串ABCD中任取3個字元排列,不可重複選取 $result = permutations('ABCD',3,true); //從陣列ABCD中任取3個字元排列,可重複選取 $result = permutations(array('A','B','C','D'),3,false); //從陣列ABCD中任取3個字元排列,不可重複選取 $result = permutations(array('A','B','C','D'),3,true); /* 第一行的結果 Array ( [0] => ABC [1] => ABD [2] => ACB [3] => ACD [4] => ADB [5] => ADC [6] => BAC [7] => BAD [8] => BCA [9] => BCD [10] => BDA [11] => BDC [12] => CAB [13] => CAD [14] => CBA [15] => CBD [16] => CDA [17] => CDB [18] => DAB [19] => DAC [20] => DBA [21] => DBC [22] => DCA [23] => DCB ) 其它三行煩請自行測試,囧rz */
/* ************************************************************** * Web: http://liaosankai.pixnet.net/blog * Licenses: MIT and GPL * source: http://www.php.happycodings.com/Algorithms/code21.html * modifier: sankai * **************************************************************/ //============================================================== // Permutations Generator 排列產生器 //-------------------------------------------------------------- // mixed $element 卻排列的元素 // int $num 選取數 // boolean $repeat 是否可重複選取元素 //-------------------------------------------------------------- // 所需函式 + permutations_string() //============================================================== function permutations($element,$num=1,$repeat=true){ if(is_array($element)){ //產生與陣列長度一樣的索引字串 $keys = join('',range(0,count($element)-1)); //取得索引字串的排列組告 $keys_arr = permutations_string($keys,$num,$repeat); //重組陣列 foreach($keys_arr as $keys){ $item = array(); $keys_len = strlen($keys); for($i=0; $i<$keys_len; $i++){ $item[] = $element[$keys[$i]]; } $result[] = $item; } return $result; } else if(is_string($element)){ return permutations_string($element,$num,$repeat); } else { die('輸入的元素必需為字串或陣列'); } } //============================================================== // 取得字串類型的排列組合 //-------------------------------------------------------------- // 所需函式 + lastchar() // + stringtoarray() // + char_add //============================================================== function permutations_string($letters,$num,$repeat=true){ if(is_string($letters)){ //算出最後一個排列結果(用來當作while迴圈的停止點) $last = str_repeat($letters{0},$num); //儲存所有排列組合的集合陣列 $result = array(); //迴圈組合排列 while($last != str_repeat(lastchar($letters),$num)){ //元素是否可以重複使用 if($repeat){ //插入新的排列結果 $result[] = $last; //過濾重複的部分 } else{ if(count(array_count_values(stringtoarray($last))) == $num){ $result[] = $last; } } //重新定義最後的排列結果(減少選取數再重跑) $last = char_add($letters,$last,$num-1); } //補上最後一個排列結果 if($repeat){ //插入新的排列結果 $result[] = $last; } else{ if(count(array_count_values(stringtoarray($last))) == $num){ $result[] = $last; } } //回傳整個排列組合的結果 return $result; } else{ return $result; } } //============================================================== // 將字串string中第char個取代為字中digits第char+1個字元位置的字元 //-------------------------------------------------------------- // 所需函式 + lastchar() // + changeall() //============================================================== function char_add($digits,$string,$char){ if($string{$char} != lastchar($digits)){ $string{$char} = $digits{strpos($digits,$string{$char})+1}; return $string; }else{ $string = changeall($string,$digits{0},$char); return char_add($digits,$string,$char-1); } } //============================================================== // 將字串轉為陣列 //============================================================== function stringtoarray($string){ $len = strlen($string); for($cur=0; $cur<$len; $cur++){ $characterarray[] = $string{$cur}; } return $characterarray; } //============================================================== // 取得字串string中最後一個字元 //============================================================== function lastchar($string){ return $string{strlen($string)-1}; } //============================================================== // 將字串$string第$start到$end個字元取代為$char //============================================================== function changeall($string,$char,$start = 0,$end = 0){ if($end == 0) $end = strlen($string)-1; for($i=$start;$i<=$end;$i++){ $string{$i} = $char; } return $string; }
全站熱搜
留言列表