Home Backend Development PHP Tutorial PHP full permutation recursive algorithm sample code

PHP full permutation recursive algorithm sample code

Jul 12, 2017 pm 02:25 PM
php code Example

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');
Copy after login

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>';
Copy after login

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!

Statement of this Website
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

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian

CakePHP Date and Time CakePHP Date and Time Sep 10, 2024 pm 05:27 PM

CakePHP Date and Time

CakePHP Project Configuration CakePHP Project Configuration Sep 10, 2024 pm 05:25 PM

CakePHP Project Configuration

CakePHP File upload CakePHP File upload Sep 10, 2024 pm 05:27 PM

CakePHP File upload

CakePHP Routing CakePHP Routing Sep 10, 2024 pm 05:25 PM

CakePHP Routing

Discuss CakePHP Discuss CakePHP Sep 10, 2024 pm 05:28 PM

Discuss CakePHP

CakePHP Quick Guide CakePHP Quick Guide Sep 10, 2024 pm 05:27 PM

CakePHP Quick Guide

How To Set Up Visual Studio Code (VS Code) for PHP Development How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

How To Set Up Visual Studio Code (VS Code) for PHP Development

See all articles