首先我在segmentfault上发了一个问题,在得到萝卜同学的回答后,我又在网上查了一些资料,最后翻译了一个讲的比较好的文章,现在把所有内容都贴到这里。
想解决一个分堆问题,比如有a,b,c三个物体,列出所有可能的组合方法。
三个物体的话有5种可能性。
function all_groups(arr){
}
输入数组:[a,b,c]
输出数组:
[
[[a],[b],[c]], [[a,b],[c]], [[a],[b,c]], [[a,c],[b]], [[abc]]
]
应该是一个需要用到动态规划,递归计算的问题。
目前遍历的时候遇到了一个问题,就是如何根据物品个数,得到所有的拆分方法。
最后从这篇文章里找到了javascript的解法:
https://blogs.msdn.microsoft.com/oldnewthing/20140324-00/?p=1413
我翻译了一部分文章内容,贴在这里:
斯特林数
将n个物体,分成k堆,总共有多少种分法。
首先我们看一下第n个物体,如果把它先拿出来,会发生什么?
第一种情况:第n个物体自己就是一堆,只有它一个。把它拿走后,剩下的问题就是把
(n-1)个物体分成(k-1)堆。所以,当得到把(n-1)个物体分成(k-1)堆的分法后,再把第n个物体自己那一堆再加上去就好了。
第二种情况:如果第n个物体不是自己一堆,它是跟其他物体混合在一堆里。那么把第n个物体从那一堆拿走以后,剩下的还是(n-1)个物体在k堆里。(因为拿走第n个物体以后,堆数并没有减少,堆里还有其他物体)。那么现在,第n个物体,可能属于k堆里的任意一堆,所以会有k种情况,你可以把第n个物体插入到k堆中的任意一堆。
我们的算法现在是这样的:
1, 先处理基本情况
2,递归调用S(n
递归调用
function Stirling(n, k, f) {
}
你可以用下面这个方法来测试
function logToConsole(s) {
}
Stirling(4, 2, logToConsole);
我们来过一遍这个函数。
前两句都是判断基本情况。
第一句是判断一下都为空的情况,这是递归的结束条件。相当于说“有几种方法可以把0个物品分成0堆”答案是“只有一种方法”(这个居然是可以做到的,数学真奇妙)
第二句是判断两种为空的情况,相当于说“有几种方法可以把n个物品分成0堆”(我们都知道0不能做除数),或者“有几种方法可以把0个物品分成k堆”,答案我也只能说“臣妾做不到啊”。
这里注意一下,第一句是不能省略的。(它确实是有一种方法的)
讨论完基本情况后,我们来看一下怎么做循环。首先我们要得到把(n-1)个物品分成(k-1)堆总共共有多少种方法。得到每种方法后,我们直接把单独为一堆的第n个物品加上去。
然后,我们要得到把(n-1)个物品分成k堆,总共有多少种方法。得到每种方法后,我们需要遍历每种方法里面的每个堆,然后把第n个物品加到遍历的每个堆里。Map方法可以给数组创建一个深拷贝,然后把第n个物品,加到每个堆里。
我们再看一下这个笨办法map是怎么工作的。
- concat
就是把元素或者数组加到已有的数组里 - map就是便利数组的每个元素,做完运算后再把结果返回去
- map的回调函数是将它的递归子数组作为第一个参数,然后将index作为第二个参数
- 因此如果我们想做一个s的深拷贝,就可以写s.map(function (t, j) { return t.concat(); }).
- 但是我们并不想做一个完全的深拷贝,而是想修改他的第i个元素,所以我们检查一下index,如果index等于i,我们就把n附上去,否则我们加一个空数组[]
- 数组修改完成后,我们把它传给回调函数f
我们可以把这部分抽出来单写一个方法:
function copyArrayOfArrays(array, indexToEdit, editor) {
}
function Stirling(n, k, f) {
}
copyArrayOfArrays
想省点内存的话,在递归时,调完回调函数以后可以直接把修改的那个元素释放掉,保存数据可以全部交给回调函数去处理。
function Stirling(n, k, f) {
}
贝尔数的话也很简单,就是一个for循环从1到n调一遍斯特林数就可以了。
function Bell(n, f) {
}