PHP full permutation algorithm implementation program code_PHP tutorial

PHP full permutation algorithm implementation program code

Randomly select m (m≤n) elements from n different elements and arrange them in a certain order, which is called from n Take an arrangement of m elements from different elements. When m=n, all permutations are called full permutations.

Introduction

For example, the total arrangement of the three elements 1, 2, and 3 is:

　1,2,3

　1,3,2

　2,1,3

　2,3,1

　3,1,2

　3,2,1

A total of 3*2*1=6 types 3!

2 formulas

The total number of permutations f(n)=n! (definition 0!=1)

Recursive algorithm

　1,2,3

　1,3,2

　2,1,3

　2,3,1

　3,2,1

　3,1,2

This is because the algorithm only considers how to output the full arrangement, but does not consider whether there is a problem with transposition. So I came up with a solution, which is to modify the transposition function

For example, if 1 2 3 is transposed, it should not be directly 3 2 1, so that 3 and 1 can be transposed directly; instead, 3 should be arranged at the front and back, and 1 2 should be in sequence

Basic Algorithm

The following introduces four types of total permutation algorithms:

　(A) Dictionary order

　(B) Increasing carry number method

　(C) Decreasing carry number method

　(D) Ortho substitution method

Implementing the full permutation algorithm

The code is as follows

header("content-type:text/html;charset=utf-8");/** * @param array $a The collection of elements to be arranged, which will change dynamically * @param array $b stores the current arrangement * @param array $M The set of elements to be arranged, equivalent to a constant, always the initial set of elements to be arranged */ function wholerange($a,$b,$M){ $range=array(); if(count($a) > 1){ $d=$b; foreach($a as $value){ $b[]=$value; $c=array_diff($M,$b); if(count($c) > 0){ $range[]=wholerange($c,$b,$M); } $b=$d; } }elseif(count($a) == 1){ foreach($a as $value){ $b[]=$value; } $onerange=""; foreach($b as $value){ $onerange.=$value; } $range[]=$onerange; } return $range; } /** * Recursive output array * * @param array $arr Array to be output * @return int Returns the number of array elements*/ function recursionarray($arr){ $i=0; foreach($arr as $value){ if(is_array($value)){ $i+=recursionarray($value); }else{ echo $value." "; $i++; } } return $i; } $a=array('A','B','C','D'); $b=array(); $range=wholerange($a,$b,$a); $count=recursionarray($range); echo "There are total ".$count."arrangements"; ?>

http://www.bkjia.com/PHPjc/941716.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/941716.htmlTechArticlePHP full permutation algorithm implementation program code randomly selects m (mn) elements from n different elements, according to a certain Arranging them in order is called an arrangement in which m elements are taken from n different elements. When...