从n个不同元素中任取m（m≤n）个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列,当m=n时所有的排列情况叫全排列.

简介如1,2,3三个元素的全排列为:

1. 1,2,3 
2. 1,3,2 
3. 2,1,3 
4. 2,3,1 
5. 3,1,2 
6. 3,2,1 

共3*2*1=6种 3！

2公式

全排列数f(n)=n!(定义0!=1)

递归算法

1. 1,2,3 
2. 1,3,2 
3. 2,1,3 
4. 2,3,1 
5. 3,2,1 
6. 3,1,2 

这是由于算法只是考虑到了如何输出全排列,而没有考虑到换位是否有问题,所以我提出了解决方案,就是换位函数修改下,如 1 2 3 换位的话,不应该直接 3 2 1这样,让3和1直接换位;而是让3排在最前后,1 2 依次向后.

基本算法

以下介绍全排列算法四种:

(A)字典序法

(B)递增进位制数法

(C)递减进位制数法

(D)邻位对换法

实现全排列算法,代码如下:

1. <?php 
2. header("content-type:text/html;charset=utf-8");/** 
3.  * @param array $a 待排列的元素集合，会动态变化 
4.  * @param array $b 储存当前排列 
5.  * @param array $M 待排列的元素集合，相当于一个常量，始终为初始待排列的元素集合 
6.  */ 
7. function wholerange($a,$b,$M){ 
8.  $range=array(); 
9.  if(count($a) > 1){ 
10.   $d=$b; 
11.   foreach($a as $value){ 
12.    $b[]=$value; 
13.    $c=array_diff($M,$b); 
14.    if(count($c) > 0){ 
15.     $range[]=wholerange($c,$b,$M); 
16.    } 
17.    $b=$d; 
18.   } 
19.  }elseif(count($a) == 1){ 
20.   foreach($a as $value){ 
21.    $b[]=$value; 
22.   } 
23.   $onerange=""; 
24.   foreach($b as $value){ 
25.    $onerange.=$value; 
26.   } 
27.   $range[]=$onerange; 
28.  } 
29.  return $range; 
30. } 
31. /** 
32.  * 递归输出数组 
33.  * 
34.  * @param array $arr 待输出的数组 
35.  * @return int 返回数组元素个数*/ 
36. function recursionarray($arr){ 
37.  $i=0; 
38.  foreach($arr as $value){ 
39.   if(is_array($value)){ 
40.    $i+=recursionarray($value); 
41.   }else{ 
42.    echo $value."<br/>"; 
43.    $i++;//开源软件:phpfensi.com 
44.   } 
45.  } 
46.  return $i; 
47. } 
48. $a=array('A','B','C','D'); 
49. $b=array(); 
50. $range=wholerange($a,$b,$a); 
51. $count=recursionarray($range); 
52. echo "总共有".$count."排列"; 
53. ?>

Tags: PHP排列算法 PHP算法

分享到：