PHP排列組合演算法

　　一直對演算法很感興趣，去年初培訓iOS的時候老師在課堂上出了個排列的題目看誰能最先說出想法，但並不要求立即編碼實現，當時北科大一同學很快說出了可行的辦法得到了老師的肯定，聽似簡單但並不是想像的那麼容易理解，後來各種事就沒有細想了。

　　其實早在大學時代我就嘗試用C寫過彩票的排列，當時玩過一段時間福彩3D和體彩排列三，企圖通過計算機來篩選可能的中獎號碼，那時才疏學淺完全是興趣驅動，幸好當時沒有經濟來源，有限的生活費被我敗光後及時走出了這條不歸路。

　　最近做的手遊專案中說是需要排列組合的演算法，我現在雖然做客戶端了但是PHP還是比較熟悉的，於是就自己練練手寫寫看，出人意料的是原來PHP的數組函數用著如此方便，這麼幾行就搞定了，現在分享給大家，不足之處還望多多指教。

<?php

// 阶乘
function factorial($n) {
	return array_product(range(1, $n));
}

// 排列数
function A($n, $m) {
	return factorial($n)/factorial($n-$m);
}

// 组合数
function C($n, $m) {
	return A($n, $m)/factorial($m);
}

// 排列
function arrangement($a, $m) {
	$r = array();

	$n = count($a);
	if ($m <= 0 || $m > $n) {
		return $r;
	}

	for ($i=0; $i<$n; $i++) {
		$b = $a;
		$t = array_splice($b, $i, 1);
		if ($m == 1) {
			$r[] = $t;
		} else {
			$c = arrangement($b, $m-1);
			foreach ($c as $v) {
				$r[] = array_merge($t, $v);
			}
		}
	}

	return $r;
}

// 组合
function combination($a, $m) {
	$r = array();

	$n = count($a);
	if ($m <= 0 || $m > $n) {
		return $r;
	}

	for ($i=0; $i<$n; $i++) {
		$t = array($a[$i]);
		if ($m == 1) {
			$r[] = $t;
		} else {
			$b = array_slice($a, $i+1);
			$c = combination($b, $m-1);
			foreach ($c as $v) {
				$r[] = array_merge($t, $v);
			}
		}
	}

	return $r;
}


// ====== 测试 ======
$a = array("A", "B", "C", "D");

$r = arrangement($a, 2);
var_dump($r);

$r = A(4, 2);
echo $r."\n";

$r = combination($a, 2);
var_dump($r);

$r = C(4, 2);
echo $r."\n";

　　另外幾年前培訓PHP的時候還寫過一個回環矩陣的算法，在此不讓使用外鏈，感興趣的同學可自行百度“月初新浪的一道關於算法的筆試題”，第二條就是我原版，供大家學習交流。

以上就介紹了PHP排列組合演算法，包含了方面的內容，希望對PHP教學有興趣的朋友有幫助。