排列组合中的分堆可能性问题

首先我在segmentfault上发了一个问题,在得到萝卜同学的回答后,我又在网上查了一些资料,最后翻译了一个讲的比较好的文章,现在把所有内容都贴到这里。

其实还是数学问题,如果知道贝尔数,斯特林数这些概念,这个问题解决起来应该还是很容易的。

问题链接:https://segmentfault.com/q/1010000010946622

想解决一个分堆问题,比如有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 − 1, k,把第n个物体依次插入k堆里的每个堆里

递归调用 S(n − 1, k − 1),第n个物体是单独一堆,把这堆直接加到后面

function Stirling(n, k, f) {

if (n == 0 && k == 0) { f([]); return; }

if (n == 0 || k == 0) { return; }

Stirling(n-1, k-1, function(s) {

f(s.concat([[n]])); // append [n] to the array

});

Stirling(n-1, k, function(s) {

for (var i = 0; i < k; i++) {

  f(s.map(function(t, j) { // append n to the i’th subarray

   return t.concat(i == j ? n : []);

  }));

}

});

}

你可以用下面这个方法来测试

function logToConsole(s) {

console.log(JSON.stringify(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) {

return array.map(function(e, i) {

return i === indexToEdit ? editor(e) : e.concat();

});

}

function Stirling(n, k, f) {

if (n == 0 && k == 0) { f([]); return; }

if (n == 0 || k == 0) { return; }

Stirling(n-1, k-1, function(s) {

f(s.concat([[n]])); // append [n] to the array

});

Stirling(n-1, k, function(s) {

for (var i = 0; i < k; i++) {

  f(copyArrayOfArrays(s, i, function(e) { return e.concat(n); }));

}

});

}

copy­Array­Of­Arrays 这个函数需要拷贝和遍历整个二维数组,然后找到index再修改那个元素

想省点内存的话,在递归时,调完回调函数以后可以直接把修改的那个元素释放掉,保存数据可以全部交给回调函数去处理。

function Stirling(n, k, f) {

if (n == 0 && k == 0) { f([]); return; }

if (n == 0 || k == 0) { return; }

Stirling(n-1, k, function(s) {

for (var i = 0; i < k; i++) {

  s[i].push(n);

  f(s);

  s[i].pop();

}

});

Stirling(n-1, k-1, function(s) {

s.push([n]);

f(s);

s.pop();

});

}

贝尔数的话也很简单,就是一个for循环从1到n调一遍斯特林数就可以了。

function Bell(n, f) {

for (var i = 1; i <= n; i++) {

Stirling(n, i, f);

}

}

 

By | 2017-09-04T12:48:17+00:00 九月 4th, 2017|技术|排列组合中的分堆可能性问题已关闭评论

About the Author: