怎么在php中實現(xiàn)一個全排列遞歸算法-創(chuàng)新互聯(lián)

怎么在php中實現(xiàn)一個全排列遞歸算法？相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)長期為近千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為措美企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、網(wǎng)站設(shè)計，措美網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

算法原理

如果用P表示n個元素的全排列，而Pi表示n個元素中不包含元素i的全排列，(i)Pi表示在排列Pi前面加上前綴i的排列，那么n個元素的全排列可遞歸定義為：
    ① 如果n=1，則排列P只有一個元素i；
    ② 如果n>1，則全排列P由排列(i)Pi構(gòu)成；
根據(jù)定義，可以看出如果已經(jīng)生成（k-1）個元素的排列Pi，那么k個元素的排列可以在每個Pi前面加上元素i而生成。
代碼實現(xiàn)

復(fù)制代碼 代碼如下:

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

不過，經(jīng)多次測試運行結(jié)果，發(fā)現(xiàn)存在一個問題：若是存在相同的元素，則全排列有重復(fù)。
例如'122'的全排列只有三種情況：'122'、'212'、'221'；上面方法卻有重復(fù)。
略修改，加個判斷重復(fù)的標(biāo)志，解決了問題（代碼如下）：

復(fù)制代碼 代碼如下:

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

看完上述內(nèi)容，你們掌握怎么在php中實現(xiàn)一個全排列遞歸算法的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

本文題目：怎么在php中實現(xiàn)一個全排列遞歸算法-創(chuàng)新互聯(lián)
文章起源：http://www.muchs.cn/article18/cshhdp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、用戶體驗、電子商務(wù)、關(guān)鍵詞優(yōu)化、網(wǎng)站改版、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)