Home >Backend Development >PHP Tutorial >PHP full permutation recursive algorithm code_PHP tutorial

PHP full permutation recursive algorithm code_PHP tutorial

WBOY
WBOYOriginal
2016-07-21 15:15:42891browse

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

Algorithm 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...
Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn