首页 » 建站技术 » PHP 技术 » 浏览内容

PHP实现排列组合


2012-11-27 23:49:23 2,239 0 发表评论 字体: 作者:C.K.

体验版 88 元,个人版 128 元,多用户版 288元个人版160元升级到多用户版。

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

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

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

文中有对公式的描述:

A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!
  • C(n,m)=A(n,m)/m!=n!/((n-m)!*m!)
  • 有这两个公式就能知道结果数量怎么算

    排列算法:

    <?php
  • function a($n, $m){
  •     if($n < $m) return false;
  •     $num = 1;
  •     for($i=0; $i<$m; $i++){
  •         $num = $num * ($n-$i);
  •     }
  •     return $num;
  • }
  • ?>
  • 组合算法:

    <?php
  • function c($n, $m){
  •     if($n < $m) return false;
  •     return a($n,$m)/a($m,$m);
  • }
  • ?>
  • 应用方法:

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

    <?php
  • function arrangement($arr, $len=0, $str="") {
  •     global $res;
  •     $arr_len = count($arr);
  •     if($len == 0){
  •         $res[] = $str;
  •     }else{
  •         for($i=0; $i<$arr_len; $i++){
  •             $tmp = array_shift($arr);
  •             arrangement($arr, $len-1, $str."\t".$tmp);
  •             array_push($arr, $tmp);
  •         }
  •     }
  • }
  • ?>
  • 组合枚举算法:

    <?php
  • function combination($arr, $len=0, $str="") {
  •     global $res;
  •     $arr_len = count($arr);
  •     if($len == 0){
  •         $res[] = $str;
  •     }else{
  •         for($i=0; $i<$arr_len-$len+1; $i++){
  •             $tmp = array_shift($arr);
  •             combination($arr, $len-1, $str."\t".$tmp);
  •         }
  •     }
  • }
  • ?>
  • 应用方法:

    <?php
  • $arr = array(1,2,3,4,5,6,7);//词根
  • $num = 2;//所需使用词根的数量
  • $res = array();结果集
  • arrangement($arr, $num);//进行排列运算
  • var_dump($res);//输出排列结果
  • $res = array();
  • combination($arr, $num);//进行组合运算
  • var_dump($res);//输出组合结果
  • ?>
  • 因为PHP的效率问题,不适宜做太大量的运算,程序的效率我个人觉得已经最优,如有不足还望高人指点。

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

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

    网站统计 Statistics

    • 创建时间: 2005年1月3日 距今5041 天
    • 日志总数: 2461
    • 评论总数: 630
    • 标签总数: 654
    • 链接总数: 273
    • 最后更新: 2018-8-31 17:57:04
    • 您是本站第 14060220 位访客

    广告区 Guǎng Gào