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，如需轉載請自行聯系原作者