php全排列遞歸算法代碼

更新時間：2012年10月09日 19:40:45 作者：

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而生成。
代碼實現(xiàn)

復制代碼代碼如下:

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');

不過，經多次測試運行結果，發(fā)現(xiàn)存在一個問題：若是存在相同的元素，則全排列有重復。
例如'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>';

您可能感興趣的文章:

遞歸算法

php簡單隨機字符串生成方法示例
這篇文章主要介紹了php簡單隨機字符串生成方法,結合實例形式分析了php生成隨機字符串的相關技巧與注意事項,需要的朋友可以參考下
2017-04-04
PHP附件下載中文名稱亂碼的解決方法
這篇文章主要介紹了PHP附件下載中文名稱亂碼的解決方法,分析了中文亂碼形成的原因及對應的編碼轉換方法,具有一定參考借鑒價值,需要的朋友可以參考下
2015-12-12
php建立Ftp連接的方法
這篇文章主要介紹了php建立Ftp連接的方法,實例分析了php操作FTP的相關函數(shù)及使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下
2015-03-03
php下MYSQL limit的優(yōu)化
MYSQL的優(yōu)化是非常重要的。其他最常用也最需要優(yōu)化的就是limit。mysql的limit給分頁帶來了極大的方便，但數(shù)據量一大的時候，limit的性能就急劇下降。
2008-01-01
php token使用與驗證示例【測試可用】
這篇文章主要介紹了php token使用與驗證方法,通過對form表單hidden提交字段的處理實現(xiàn)token驗證功能,防止非法來源數(shù)據的訪問,需要的朋友可以參考下
2017-08-08
PHP獲取表單所有復選框的值的方法
這篇文章主要介紹了PHP獲取表單所有復選框的值的方法,是進行PHP程序設計表單操作中所必須掌握的常用技巧,需要的朋友可以參考下
2014-08-08
php數(shù)據結構之順序鏈表與鏈式線性表示例
這篇文章主要介紹了php數(shù)據結構之順序鏈表與鏈式線性表,結合實例形式較為詳細的分析了php實現(xiàn)順序鏈表與鏈式線性表的各種常用操作技巧,需要的朋友可以參考下
2018-01-01
php將圖片保存入mysql數(shù)據庫失敗的解決方法
這篇文章主要介紹了php將圖片保存入mysql數(shù)據庫失敗的解決方法,詳細分析了php將圖片保存入數(shù)據庫遇到的問題及對應的解決方法,并總結了相關的技巧,具有一定的參考借鑒價值,需要的朋友可以參考下
2014-12-12
php實現(xiàn)簡單的MVC框架實例
這篇文章主要介紹了php實現(xiàn)簡單的MVC框架,較為詳細的分析了php實現(xiàn)MVC框架的相關實現(xiàn)技巧與注意事項,具有一定參考借鑒價值,需要的朋友可以參考下
2015-09-09
PHP通過GD庫實現(xiàn)驗證碼功能示例
這篇文章主要介紹了PHP通過GD庫實現(xiàn)驗證碼功能,結合實例形式分析了php驗證碼相關圖片繪制、輸出操作實現(xiàn)技巧,需要的朋友可以參考下
2019-02-02