PHP full permutation recursive algorithm code_PHP tutorial

Algorithm Principle

If P represents the complete arrangement of n elements, and Pi represents the complete arrangement of n elements that does not include element i, (i) Pi represents adding in front of the arrangement Pi For the arrangement prefixed with i, then the total arrangement of n elements can be recursively defined as:
① If n=1, then the arrangement P has only one element i;
② If n>1, then the total arrangement P is (i) Pi composition;
According to the definition, it can be seen that if the arrangement Pi of (k-1) elements has been generated, then the arrangement of k elements can be generated by adding element i in front of each Pi.
Code implementation

Copy code The code is as follows:

function rank($base, $temp=null)
{
$len = strlen($base);
if($len <= 1)
{
echo $temp.$base.'
';
}
else
{
for($i=0; $i< $len; ++$i)
{
rank(substr($base, 0, $i ).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
                                         123');


However, after multiple test runs, it was found that there is a problem: if there are the same elements, the entire arrangement will be repeated.
For example, there are only three situations for the full arrangement of '122': '122', '212', and '221'; but the above methods are repeated.

Slightly modified, added a flag to identify duplicates, solved the problem (the code is as follows):



Copy the code

The code is as follows: function fsRank($base, $temp=null)

{

static $ret = array();
$len = strlen($base);
if($len < = 1)
{
//echo $temp.$base.'
';
$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;
                                                                                                        }
                                                                                                                                                                      ; i+1, $len-$i-1), $temp.$base[$i]);
}
}
return $ret;
}
print '< pre>';
print_r(fsRank('122'));
print '';






http://www.bkjia.com/PHPjc/326052.html

www.bkjia.com

true

http: //www.bkjia.com/PHPjc/326052.html

TechArticleAlgorithm Principle If P is used to represent the full arrangement of n elements, and Pi represents that the n elements do not contain element i The total arrangement of n, (i) Pi represents the arrangement with the prefix i in front of the arrangement Pi, then the total arrangement of n elements...