PHP full permutation recursive algorithm sample code
Jul 12, 2017 pm 02:25 PMRecursion 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!

Hot Article

Hot tools Tags

Hot Article

Hot Article Tags

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian

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