学步园

算法原理：

问题为从m个数中取n个数，先从m个数中取第1个数，问题归结为从m-1个数中取n-1个，再从m-1个数中取第二个数，问题归结为从m-2个数中取n-2个，... 以此类推，用递归实现。 

<?php
/**
 * @类名: Permutation
 * @功能：求从m个数中取任取n个数的的排列和组合
 * @作者：johnpanq
 * @创建：2006.2.23
 * @更新：2007.1.26
 * @示例：
 * $m = array(1,2,3);
 * $num = new Permutation($m);
 * getList($n,$order=1) $n为取得个数，$order=1为排列，$order=2为组合
 * 如取两个数的排列
 * $arr = $num->getList(2);
 * 如取两个数的组合
 * $arr = $num->getList(2,2);
 * $arr排列组合的二维数组
 */
class Permutation
{
    var $srcList;    //存放原始数列数组
    var $rstList;    //存放最终数列数组
    var $srcLen;    //原始数列的长度
    var $rstLen;    //结果数列的长度
    var $rstOrder;    //求排列或组合标志

    function Permutation($m)
    {
        if (!is_array($m))
        {
            echo '参数类型错误：Permutation(array $m) $m为数组类型';
            return false;
        }
        $this->srcLen    = count($m);
        $this->srcList    = $m;
    }
    
    //取得排列组合结果, $order=1为取排列,$order=2为取组合
    function getList($n, $order=1)
    {
        if (!is_int($n))
        {
            echo '参数类型错误：getList(int $n) $n为整数类型';
            return false;
        }
        if ($n > $this->srcLen)
        {
            echo '要求的排列组合的长度不能大于原始数列的长度';
            return false;
        }        
        $this->rstLen   = $n;
        $this->rstOrder = $order;
        $this->rstList  = array();
        $this->doPermutation($this->srcList, $this->rstLen);
        return $this->rstList;
    }
    
    //递归计算从m中取n的排列, $rst存取出的排列
    function doPermutation($m, $n, &$rst=array())
    {
        //如果已经取完
        if ($n == 0)
        {
            $this->rstList[] = $rst;
            $rst = array();
            return true;
        }
        //从当前数列m中选取一个值，并更新数列m
        foreach($m as $key=>$value)
        {
            $nextM = $m;
            //判断是取排列还是组合
            switch($this->rstOrder)
            {
                //取排列, 清空当前取出的值
                case 1: unset($nextM[$key]); break;
                //取组合, 清空当前及前面所取的值
                case 2: array_splice($nextM,0,$key+1); break;
                default:unset($nextM[$key]); break;
            }
            $nextRst = $rst;
            //将取的值放到结果数列中
            $nextRst[] = $value;
            $this->doPermutation($nextM,$n-1,$nextRst);
        }
    }
}

$m = array(0,1,2,3,4,5);
$num = new Permutation($m);
$arr = $num->getList(4);
foreach($arr as $value)
{
    echo implode(",",$value)."<br>";
}
?>