问题
对于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，在[2,3,4,5]中寻找另一个数，得到4组
-
放弃1，控制2，在[3,4,5]中寻找另一个数，得到3组
-
放弃[1,2]，控制3，在[4,5]中寻找另一个数，得到2组
-
放弃[1,2,3]，控制4，只剩下5一个数可选了，得到1组，结束穷举，得到10组
没有感觉，再看一个，比如5取3：
-
控制[1,2]，在[3,4,5]中寻找另一个数，直到末尾，得到3组
-
控制[1,3]，在[4,5]中寻找另一个数，直到末尾，得到2组
-
控制[1,4]，只剩下5一个数可选了，得到1组
-
放弃1，控制[2,3]，在[4,5]中寻找另一个数，直到末尾，得到2组
-
放弃1，控制[2,4]，只剩下5一个数可选了，得到1组
-
放弃1、2，控制[3,4]，只剩下5一个数可选了，得到1组，结束穷举，总共10组
你可能觉得有感觉了，再来，比如看5取4：
-
控制[1,2,3]，在[4,5]中寻找另一个数，得到两组
-
控制[1,2,4]，只剩下一个5可选，得到一组
-
控制[1,3,4]，只剩下一个5可选，得到一组
-
放弃1，控制[2,3,4]，只剩下一个5可选，得到一组，结束穷举，总共5组
我们可以尝试着发现以下结论（也许存在无用的结论）：
-
控制的个数=要取出的个数-1
-
当只剩下一个数可选时，意味着要更换控制的数
-
当控制的数改变到最左侧时，意味着要放弃一个数
-
当【放弃的个数+要取出的个数=总个数】时，意味着穷举结束
程序方面，我们可以联想到，输入函数的参数应该只有两个：
-
等待穷举的数组
-
需要取出的个数
返回值就是一个二维数组，每组数代表一种组合。
可是，到了这里好像问题还是毫无头绪。
我们再回去仔细观察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) 输出的结果和人为穷举相同
那要如何通过递归把这三种情况扩展呢，我们作如下分析（需要较强的编程基础）：
-
我们必须也用变量代表要取出的数量，也就是 n 取 m，所以输入的参数就是 n 和 m
-
我们要以 p 取1的结果作为基础推出上层结果，所以递归深入的边际条件就是，m-递归次数=1
-
我们每次向上层返回的结果，取出的个数并不固定，所以也必须用变量表示下标，以此来组合新的结果（这是一个观察结论）
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;
}
}
//测试了几种常见情况，返回结果均正确
解答
我们现在有了获取穷举数组下标的方法，回到最开始的问题
我们需要输入函数的参数应该是：
-
等待穷举的数组
-
需要取出的个数
所以最终的函数：
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个，结果完全正确
最后
当我写完这篇文章时，我上网查了一下，网上的写法和我的差别是非常大的，可以说基本看不懂其他人的思路。
所以，我认为这个算法肯定是存在优化的空间的，可能存在更加巧妙的方法，欢迎讨论。
另外，你可能会想，穷举排列（分先后顺序）的算法会不会比这个更复杂，但其实比这个要简单的多。可以尝试想一下，很快就能想出来。
那么这个算法在多规格商品检索中到底有什么用呢，嗯，这个题目又可以开一个新坑了。
网友评论