如何在javascript中将集合的元素分为不相交的子集？

Question

一个9人小组可以以几种方式在2个，3个和4个不相交的亚组中工作？如何通过javascript回溯生成所有可能性。

例：

Gs = group([aldo,beat,carla,david,evi,flip,gary,hugo,ida],[2,2,5]);

console.log(Gs); // [[aldo,beat],[carla,david],[evi,flip,gary,hugo,ida]], ...

请注意，我不希望组成员进行排列。即[[aldo，beat]，...]与[[beat，aldo]，...]相同。但是，[[aldo，beat]，[carla，david]，...]和[[carla，david]，[aldo，beat]，...]之间存在差异。

*请没有图书馆。

Answer 1

如果您只需要将9人组成的小组划分为2个，3个和4个人的3个子组的方式，那么使用数学方法C（计算组合数的函数）就很容易计算。

1. 首先，您有9个人，您需要选择2个人。因此你做C(9, 2)。
2. 接下来，您有7个人，您需要选择3个人。因此你做C(7, 3)。
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操作员理想的选择。因此，我们要做的第一件事就是用ambJavaScript 编写运算符：

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/