程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> PHP綜合 >> php全排列遞歸算法代碼

php全排列遞歸算法代碼

編輯:PHP綜合
算法原理

如果用P表示n個元素的全排列,而Pi表示n個元素中不包含元素i的全排列,(i)Pi表示在排列Pi前面加上前綴i的排列,那麼n個元素的全排列可遞歸定義為:
    ① 如果n=1,則排列P只有一個元素i;
    ② 如果n>1,則全排列P由排列(i)Pi構成;
根據定義,可以看出如果已經生成(k-1)個元素的排列Pi,那麼k個元素的排列可以在每個Pi前面加上元素i而生成。
代碼實現
復制代碼 代碼如下:
function rank($base, $temp=null)
{
    $len = strlen($base);
    if($len <= 1)
    {
        echo $temp.$base.'<br/>';
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
}
rank('123');

不過,經多次測試運行結果,發現存在一個問題:若是存在相同的元素,則全排列有重復。
例如'122'的全排列只有三種情況:'122'、'212'、'221';上面方法卻有重復。
略修改,加個判斷重復的標志,解決了問題(代碼如下):
復制代碼 代碼如下:
function fsRank($base, $temp=null)
{
    static $ret = array();
    $len = strlen($base);
    if($len <= 1)
    {
        //echo $temp.$base.'<br/>';
        $ret[] = $temp.$base;
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            $had_flag = false;
            for($j=0; $j<$i; ++$j)
            {
                if($base[$i] == $base[$j])
                {
                    $had_flag = true;
                    break;
                }
            }
            if($had_flag)
            {
                continue;
            }
            fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
    return $ret;
}
print '<pre>';
print_r(fsRank('122'));
print '</pre>';

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved