php对数组进行全排列的非递归算法


  1. /**
  2. * 取得数组的全排列
  3. *
  4. * @author ustb80
  5. * @param array $source 待排列数组,一维
  6. * @return array
  7. */
  8. function getAllPerm($source
  9.     $rs = array(); 
  10.     sort($source); 
  11.     $last = count($source) - 1; 
  12.     $z = 0; 
  13.     $x = $last
  14.     $rs[] = $source
  15.  
  16.     while($x > 0) 
  17.     { 
  18.         // 相邻的两个元素,先将x的值赋给y,x再自减1 
  19.         $y = $x--; 
  20.  
  21.         // 如果前一个元素的值小于后一个元素的值 
  22.         if($source[$x] < $source[$y]) 
  23.         { 
  24.             // 从尾部开始,找到第一个大于 $x 元素的值 
  25.             $z = $last
  26.             while($source[$x] > $source[$z]) 
  27.             { 
  28.                 $z--; 
  29.             } 
  30.  
  31.             // 交换 $x 和 $z 元素的值 
  32.             list($source[$x], $source[$z]) = array($source[$z], $source[$x]); 
  33.  
  34.             // 将 $y 之后的元素全部逆向排列 
  35.             for($i = $last$i > $y$i--, $y++) 
  36.             { 
  37.                 list($source[$i], $source[$y]) = array($source[$y], $source[$i]); 
  38.             } 
  39.             $rs[] = $source
  40.             $x = $last
  41.         } 
  42.     } 
  43.     return $rs
  44.  
  45. $source = array(1,2,3); 
  46. $rs = getAllPerm($source); 
  47. print_r($rs); 

输出结果:


  1. Array 
  2.     [0] => Array 
  3.         ( 
  4.             [0] => 1 
  5.             [1] => 2 
  6.             [2] => 3 
  7.         ) 
  8.  
  9.     [1] => Array 
  10.         ( 
  11.             [0] => 1 
  12.             [1] => 3 
  13.             [2] => 2 
  14.         ) 
  15.  
  16.     [2] => Array 
  17.         ( 
  18.             [0] => 2 
  19.             [1] => 1 
  20.             [2] => 3 
  21.         ) 
  22.  
  23.     [3] => Array 
  24.         ( 
  25.             [0] => 2 
  26.             [1] => 3 
  27.             [2] => 1 
  28.         ) 
  29.  
  30.     [4] => Array 
  31.         ( 
  32.             [0] => 3 
  33.             [1] => 1 
  34.             [2] => 2 
  35.         ) 
  36.  
  37.     [5] => Array 
  38.         ( 
  39.             [0] => 3 
  40.             [1] => 2 
  41.             [2] => 1 
  42.         ) 
  43.  









本文转自 ustb80 51CTO博客,原文链接:http://blog.51cto.com/ustb80/1033843,如需转载请自行联系原作者
上一篇:next_permutation(全排列算法)


下一篇:函数调用运算符