如果您只需要一组 9 人可以分为 2、3 和 4 人的 3 个子组,那么这很容易使用数学计算C
(计算组合数的函数)。
- 首先,您有 9 个人,您需要从中选择 2 个人。因此你这样做
C(9, 2)
。
- 接下来你有 7 个人,你需要从中选择 3 个人。因此你这样做
C(7, 3)
。
- 最后你有4个人,你需要从中选择4个人。因此你这样做
C(4, 4)
。但是C(n, n)
始终为 1。
因此,将一组 9 人分成 2、3 和 4 人的 3 个子组的方法数是C(9, 2) * C(7, 3) * C(4, 4)
。这可以简化为C(9, 2) * C(7, 3)
,也36 * 35
就是1260
。
我们可以编写一个函数来为我们计算:
function ways(n) {
var l = arguments.length, w = 1;
for (var i = 1; i < l; i++) {
var m = arguments[i];
w *= combinations(n, m);
n -= m;
}
return w;
}
为了使这个函数工作,我们需要定义函数combinations
:
function combinations(n, k) {
return factorial(n) / factorial(n - k) / factorial(k);
}
最后我们需要为 定义函数factorial
:
function factorial(n) {
var f = n;
while (--n) f *= n;
return f;
}
然后我们计算方式的数量如下:
alert(ways(9, 2, 3)); // 1260
你可以在这里看到演示:http: //jsfiddle.net/bHSuh/
请注意,我们不需要指定最后一个由 4 人组成的子组,因为这是隐含的。
但是我相信你想产生每一种可能的方式。amb
这是运营商最适合的事情。所以我们要做的第一件事是用amb
JavaScript 编写运算符:
function amb(options, callback) {
var length = options.length;
for (var i = 0; i < length; i++) {
try {
callback(options[i]); // try the next option
return; // no problem, quit
} catch (e) {
continue; // problem, next
}
}
throw new Error("amb tree exhausted"); // throw a tantrum
}
接下来我们将编写一个函数,从索引列表中选择一组给定的项目:
function pick(list, items) {
var length = list.length, selected = [], rest = [];
for (var i = 0; i < length; i++) {
if (items.indexOf(i) < 0) rest.push(list[i]);
else selected.push(list[i]);
}
return [selected, rest];
}
我们还需要一个生成索引列表的函数:
function getIndices(length) {
var indices = [];
for (var i = 0; i < length; i++)
indices.push(i);
return indices;
}
最后,我们将group
递归地实现该函数:
function group(options, divisions) {
var subgroup = [], groups = [], n = 0;
var indices = getIndices(options.length);
var division = divisions.shift(), remaining = divisions.length;
try {
amb(indices, select);
} catch (e) {
return groups;
}
function select(index) {
subgroup.push(index);
if (++n < division) {
try { amb(indices.slice(index + 1), select); }
catch (e) { /* we want to continue processing */ }
} else {
var subgroups = pick(options, subgroup);
if (remaining) {
var children = group(subgroups.pop(), divisions.slice());
var length = children.length;
for (var i = 0; i < length; i++)
groups.push(subgroups.concat(children[i]));
} else groups.push(subgroups);
}
n--;
subgroup.pop();
throw new Error;
}
}
现在您可以按如下方式使用它:
var groups = group([
"aldo", "beat", "carla",
"david", "evi", "flip",
"gary", "hugo", "ida"
], [2, 3]);
再次注意,您不需要指定最后一个由 4 人组成的子组,因为它是隐含的。
现在让我们看看输出是否如我们预期的那样:
console.log(groups.length === ways(9, 2, 3)); // true
你去吧。正好有 1260 种方法可以将一组 9 人分为 3 个子组,每个子组 2、3 和 4 人。
现在我知道我的group
函数看起来有点吓人,但实际上非常简单。尝试阅读并了解发生了什么。
想象一下,你是 9 个人的老板。您如何将他们分成 2、3 和 4 人的 3 个子组?这正是我的group
功能的工作方式。
如果一段时间后您仍然无法理解逻辑,那么我将更新我的答案并group
详细解释该功能。祝你好运。
顺便说一句,我刚刚意识到对于这个问题,你并不真正需要amb
. 您可以简单地使用forEach
。由于没有 try-catch 块,生成的代码会更快:
function group(options, divisions) {
var subgroup = [], groups = [], n = 0;
var indices = getIndices(options.length);
var division = divisions.shift(), remaining = divisions.length;
indices.forEach(select);
return groups;
function select(index) {
subgroup.push(index);
if (++n < division) indices.slice(index + 1).forEach(select);
else {
var subgroups = pick(options, subgroup);
if (remaining) {
var children = group(subgroups.pop(), divisions.slice());
var length = children.length;
for (var i = 0; i < length; i++)
groups.push(subgroups.concat(children[i]));
} else groups.push(subgroups);
}
subgroup.pop();
n--;
}
}
由于我们不再使用amb
,程序的执行时间减少了十倍。亲自查看结果:http: //jsperf.com/amb-vs-foreach
此外,我终于创建了上述程序的演示小提琴:http: //jsfiddle.net/Ug6Pb/