本篇程式有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;
}

低溫烘培 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • hsinchen
  • 拿去用囉,感謝~~