全排列递归算法

27_Man

全排列递归算法

    <div class="postText"><div id="cnblogs_post_body"><ul>算法原理

如果用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而生成。
代码实现

<div class="cnblogs_code">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');