PHP实现排列组合

林继 PHP 技术 2,322 共写了812个字 (2012-11-27 23:49:23) 没有评论 打印 扫描二维码 百度已收录

昨天朋友问有没有可能随机排列若干词根的软件?
我还真没有接触过类似软件,但是想了下应该需求不难,就答应帮他写一个。

开始些的时候才发现什么排列组合都还给老师了,连公式都忘记了,于是想偷懒点去Google搜索一个算法了事;一搜索才发现排列算法确实有说,但是也不是很完善,只能实现A(5,5)这样的需求,不能实现A(5,3)这样的需求,组合更加是没有搜索到;无奈只能自己写了。

先从新了解排列组合算法(百度百科中排列组合的知识http://baike.baidu.com/view/738955.htm);惊奇的发现原来排列已经由P:Permutation改成了A:Arrangement,看来以后教育宝宝会出现沟通问题了,哈哈。

文中有对公式的描述:

  1. A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!
  2. C(n,m)=A(n,m)/m!=n!/((n-m)!*m!)

有这两个公式就能知道结果数量怎么算

排列算法:

  1. <?php
  2. function a($n, $m){
  3. 	if($n < $m) return false;
  4. 	$num = 1;
  5. 	for($i=0; $i<$m; $i++){
  6. 		$num = $num * ($n-$i);
  7. 	}
  8. 	return $num;
  9. }
  10. ?>

组合算法:

  1. <?php
  2. function c($n, $m){
  3. 	if($n < $m) return false;
  4. 	return a($n,$m)/a($m,$m);
  5. }
  6. ?>

应用方法:

  1. <?php echo a(5,3) ?>
  2. <?php echo c(5,3) ?>

上面只能得到结果的数量不能枚举所有情况,继续考虑他的逻辑,最后得到枚举算法(似乎说的很简单,不过思考逻辑不好描述,程序中看端倪吧)
排列枚举算法:

  1. <?php
  2. function arrangement($arr, $len=0, $str="") {
  3. 	global $res;
  4. 	$arr_len = count($arr);
  5. 	if($len == 0){
  6. 		$res[] = $str;
  7. 	}else{
  8. 		for($i=0; $i<$arr_len; $i++){
  9. 			$tmp = array_shift($arr);
  10. 			arrangement($arr, $len-1, $str."\t".$tmp);
  11. 			array_push($arr, $tmp);
  12. 		}
  13. 	}
  14. }
  15. ?>

组合枚举算法:

  1. <?php
  2. function combination($arr, $len=0, $str="") {
  3. 	global $res;
  4. 	$arr_len = count($arr);
  5. 	if($len == 0){
  6. 		$res[] = $str;
  7. 	}else{
  8. 		for($i=0; $i<$arr_len-$len+1; $i++){
  9. 			$tmp = array_shift($arr);
  10. 			combination($arr, $len-1, $str."\t".$tmp);
  11. 		}
  12. 	}
  13. }
  14. ?>

应用方法:

  1. <?php
  2. $arr = array(1,2,3,4,5,6,7);//词根
  3. $num = 2;//所需使用词根的数量
  4. $res = array();结果集
  5. arrangement($arr, $num);//进行排列运算
  6. var_dump($res);//输出排列结果
  7.  
  8. $res = array();
  9. combination($arr, $num);//进行组合运算
  10. var_dump($res);//输出组合结果
  11. ?>

因为PHP的效率问题,不适宜做太大量的运算,程序的效率我个人觉得已经最优,如有不足还望高人指点。

最后给出我做的一个demo的地址 http://www.honglei.net/demo/aandc.php

给朋友后他非常满意,还说这个在Taobao能卖钱,似乎是什么选关键词可以用;如果有需要的朋友就直接用吧,能帮上大家的忙我也很开心。

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

< >