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

/**

* 取得数组的全排列

*

* @author ustb80

* @param array $source 待排列数组，一维

* @return array

*/

function getAllPerm($source) 

{ 

    $rs = array(); 

    sort($source); 

    $last = count($source) - 1; 

    $z = 0; 

    $x = $last; 

    $rs[] = $source; 

    while($x > 0) 

    { 

        // 相邻的两个元素，先将x的值赋给y，x再自减1 

        $y = $x--; 

        // 如果前一个元素的值小于后一个元素的值 

        if($source[$x] < $source[$y]) 

        { 

            // 从尾部开始，找到第一个大于 $x 元素的值 

            $z = $last; 

            while($source[$x] > $source[$z]) 

            { 

                $z--; 

            } 

            // 交换 $x 和 $z 元素的值 

            list($source[$x], $source[$z]) = array($source[$z], $source[$x]); 

            // 将 $y 之后的元素全部逆向排列 

            for($i = $last; $i > $y; $i--, $y++) 

                list($source[$i], $source[$y]) = array($source[$y], $source[$i]); 

            $rs[] = $source; 

            $x = $last; 

        } 

    } 

    return $rs; 

} 

$source = array(1,2,3); 

$rs = getAllPerm($source); 

print_r($rs); 

输出结果：

Array 

( 

    [0] => Array 

        ( 

            [0] => 1 

            [1] => 2 

            [2] => 3 

        ) 

    [1] => Array 

            [1] => 3 

            [2] => 2 

    [2] => Array 

            [0] => 2 

            [1] => 1 

    [3] => Array 

            [2] => 1 

    [4] => Array 

            [0] => 3 

    [5] => Array 

) 

本文转自 ustb80 51CTO博客，原文链接：http://blog.51cto.com/ustb80/1033843，如需转载请自行联系原作者