问题

对于5个数字的集合[1,2,3,4,5]，从中取出3个，不分先后，共有多少种取法？

这是一个很简单的组合问题，在之前的文章中就解决过：PHP经典面试题：上台阶问题。

结果是有10种取法，那么新的问题来了，请问分别是哪10种取法？

你可能会说这是个很简单的问题，答案脱口而出，[1,2,3]、[1,2,4]、[1,2,5]、[2,3,4]...

但是当我们需要用程序复制这个思考过程，或者说分解人们是如何进行穷举的思维时，你会发现这并不简单！

只要成功实现了这一过程，我们就可以把问题推广到，5个中取2个、5个中取4个、6个中取3个等等

在解决多规格商品查询的问题时，这个算法是可行的解决方案之一

分析

一般情况是怎样的，比如5取2：

1. 控制1，在[2,3,4,5]中寻找另一个数，得到4组

2. 放弃1，控制2，在[3,4,5]中寻找另一个数，得到3组

3. 放弃[1,2]，控制3，在[4,5]中寻找另一个数，得到2组

4. 放弃[1,2,3]，控制4，只剩下5一个数可选了，得到1组，结束穷举，得到10组

没有感觉，再看一个，比如5取3：

1. 控制[1,2]，在[3,4,5]中寻找另一个数，直到末尾，得到3组

2. 控制[1,3]，在[4,5]中寻找另一个数，直到末尾，得到2组

3. 控制[1,4]，只剩下5一个数可选了，得到1组

4. 放弃1，控制[2,3]，在[4,5]中寻找另一个数，直到末尾，得到2组

5. 放弃1，控制[2,4]，只剩下5一个数可选了，得到1组

6. 放弃1、2，控制[3,4]，只剩下5一个数可选了，得到1组，结束穷举，总共10组

你可能觉得有感觉了，再来，比如看5取4：

1. 控制[1,2,3]，在[4,5]中寻找另一个数，得到两组

2. 控制[1,2,4]，只剩下一个5可选，得到一组

3. 控制[1,3,4]，只剩下一个5可选，得到一组

4. 放弃1，控制[2,3,4]，只剩下一个5可选，得到一组，结束穷举，总共5组

我们可以尝试着发现以下结论（也许存在无用的结论）：

1. 控制的个数=要取出的个数-1

2. 当只剩下一个数可选时，意味着要更换控制的数

3. 当控制的数改变到最左侧时，意味着要放弃一个数

4. 当【放弃的个数+要取出的个数=总个数】时，意味着穷举结束

程序方面，我们可以联想到，输入函数的参数应该只有两个：

1. 等待穷举的数组

2. 需要取出的个数

返回值就是一个二维数组，每组数代表一种组合。

可是，到了这里好像问题还是毫无头绪。

我们再回去仔细观察5取3时候的控制数，它的控制数其实是，除了5之外的4个数进行了一次4取2的结果。

那4取2的控制数呢，分析后发现，其实就是3取1的结果。

初步结论

所以，当我们在5取3时，其实可以看做先做3取1，再用3取1的结果做4取2，再用4取2的结果做5取3。

换一种思路，我们要求10取4的穷举时，就得先求9取3，进而得先求8取2，最后落到7取1。再从7取1的结果推出，8取2的结果，进而推出9取3，最后得到10取4的解。

可以总结为，将任何穷举问题首先化简到 n 取1，再层层推出上级的结果。

其实，看到这个结论，就明白要用递归了，但是没有奥数大神思维的我们还是一步一步来。

为什么一定要化简到 n 取1的问题呢，那是因为程序中的循环只会取1。

从最简单的开始，我们尝试写一个 n 取1的函数：

function one($count){
    for ($i=1;$i<=$count;$i++){
        $rst[] = [$i];
    }
    return $rst;
}
//运行one(3)输出 [[1],[2],[3]]

我们通过上面的思路尝试写一个 n 取2的函数：

function two($count){
    $rst = one($count - 1);//用到前面 n 取1的结果
    foreach($rst as $v){
        for ($i=$v[0]+1;$i<=$count;$i++){
            $v[1] = $i;
            $result[] = $v;
        }
    }
return $result;
}
//运行 two(4) 输出[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

我们把这种情况扩展到 n 取3：

function three($count){
    $rst = two($count - 1);//用到前面 n 取2的结果
    foreach($rst as $v){
        for ($i=$v[1]+1;$i<=$count;$i++){
            $v[2] = $i;
            $result[] = $v;
        }
    }
    return $result;
}
//运行 three(5) 输出的结果和人为穷举相同

那要如何通过递归把这三种情况扩展呢，我们作如下分析（需要较强的编程基础）：

1. 我们必须也用变量代表要取出的数量，也就是 n 取 m，所以输入的参数就是 n 和 m

2. 我们要以 p 取1的结果作为基础推出上层结果，所以递归深入的边际条件就是，m-递归次数=1

3. 我们每次向上层返回的结果，取出的个数并不固定，所以也必须用变量表示下标，以此来组合新的结果（这是一个观察结论）

PHP经典面试题：穷举问题

观察结论

所以我们的递归函数就是：

function getAnswer($amount, $need){
    if($need == 1){
        for ($i=1;$i<=$amount;$i++){
            $rst[] = [$i];
        }
        return $rst;
    }else{
        $rst = getAnswer($amount-1, $need-1);
        foreach($rst as $v){
            for ($i=$v[$need-2]+1;$i<=$amount;$i++){
                $v[$need-1] = $i;
                $result[] = $v;
            }
        }
        return $result;
    }
}
//测试了几种常见情况，返回结果均正确

解答

我们现在有了获取穷举数组下标的方法，回到最开始的问题

我们需要输入函数的参数应该是：

1. 等待穷举的数组

2. 需要取出的个数

所以最终的函数：

function getFinallyAnswer($array, $pick){
    $amount = count($array);
    $sub = getAnswer($amount, $pick);
    foreach ($sub as $k => $v){
        foreach ($v as $per_sub){
            $rst[$k][] = $array[$per_sub - 1];
        }
    }
    return $rst;
}
//getFinallyAnswer([7,8,9,10], 3)
//我们可以尝试一下从[7,8,9,10]中任取3个，结果完全正确

最后

当我写完这篇文章时，我上网查了一下，网上的写法和我的差别是非常大的，可以说基本看不懂其他人的思路。

所以，我认为这个算法肯定是存在优化的空间的，可能存在更加巧妙的方法，欢迎讨论。

另外，你可能会想，穷举排列（分先后顺序）的算法会不会比这个更复杂，但其实比这个要简单的多。可以尝试想一下，很快就能想出来。

那么这个算法在多规格商品检索中到底有什么用呢，嗯，这个题目又可以开一个新坑了。