PHP full permutation recursive algorithm sample code

Recursion is an important programming technique. This method is used to let a function call itself from within. One example is calculating factorials. The factorial of 0 is specifically defined as 1. The factorial of a larger number is found by calculating 1 * 2 * ..., increasing by 1 each time, until the number whose factorial is to be calculated is reached.

Algorithm Principle
If P represents the full arrangement of n elements, and Pi represents the full arrangement of n elements that does not include element i, (i) Pi represents the arrangement If Pi is preceded by the prefix i, then the full 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 full arrangement P consists of the permutation (i)Pi;
According to the definition, it can be seen that if the permutation Pi of (k-1) elements has been generated, then the permutation of k elements can be generated by adding element i in front of each Pi .
Code Implementation

The code is as follows:

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 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 method is repeated.
Slightly modified, added a flag to determine duplication, solved the problem (the code is as follows):

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

The above is the detailed content of PHP full permutation recursive algorithm sample code. For more information, please follow other related articles on the PHP Chinese website!