php full permutation recursive algorithm code
- 2020-05-26 08:03:15
- OfStack
Algorithm principle
If P is used to represent the full arrangement of n elements, and Pi is used to represent the full arrangement of i elements not included in n elements, (i)Pi is used to represent the arrangement of Pi elements prefixed with i, then the full arrangement of n elements can be recursively defined as:
If n=1, then P has only one element, i.
(2) if n > 1, P is composed of i and Pi.
By definition, it can be seen that if an Pi arrangement of (k-1) elements has been generated, then an k arrangement of elements can be generated by prefacing each Pi with the element i.
Code implementation
However, after several test runs, there is a problem: if the same elements exist, the whole arrangement is repeated.
For example, '122' has only three permutations: '122', '212', '221'; The above method is repetitive.
Slightly modified and added a mark to judge the repetition, which solved the problem (the code is as follows) :
If P is used to represent the full arrangement of n elements, and Pi is used to represent the full arrangement of i elements not included in n elements, (i)Pi is used to represent the arrangement of Pi elements prefixed with i, then the full arrangement of n elements can be recursively defined as:
If n=1, then P has only one element, i.
(2) if n > 1, P is composed of i and Pi.
By definition, it can be seen that if an Pi arrangement of (k-1) elements has been generated, then an k arrangement of elements can be generated by prefacing each Pi with the element i.
Code implementation
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');
However, after several test runs, there is a problem: if the same elements exist, the whole arrangement is repeated.
For example, '122' has only three permutations: '122', '212', '221'; The above method is repetitive.
Slightly modified and added a mark to judge the repetition, which solved the problem (the code is as follows) :
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>';