更新:我完全低估了问题的严重性。无法计算，至少在2018年和可预见的 future ! 😂
给定
SET = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
和
SUBSET_SIZES = [3, 2, 2]
我想找到 SET 的所有可能的分组/子集组合，由 SUBSET_SIZES 确定，同时用完原始集中的所有项目。
上述输入的结果如下所示:
[['a', 'b', 'c'], ['d', 'e'], ['f', 'g']],
[['a', 'b', 'c'], ['d', 'f'], ['e', 'g']],
[['a', 'b', 'c'], ['d', 'g'], ['e', 'f']],
[['a', 'b', 'c'], ['e', 'f'], ['d', 'g']],
[['a', 'b', 'c'], ['e', 'g'], ['d', 'f']],
[['a', 'b', 'c'], ['f', 'g'], ['d', 'e']],
[['a', 'b', 'd'], ['c', 'e'], ['f', 'g']],
[['a', 'b', 'd'], ['c', 'f'], ['e', 'g']],
[['a', 'b', 'd'], ['c', 'g'], ['e', 'f']],
[['a', 'b', 'd'], ['e', 'f'], ['c', 'g']],
... and 200 more ...
我的实际数据集会更大(约 50 个项目)，每个子集大小将在 4 到 6 个项目之间变化，因此我正在寻找一种相当有效的方法来找到组合。不过，我可以接受需要 2-3 分钟来完成更大的数据集。
我想用 JavaScript 实现它，所以如果您已经知道可以完成这项工作的 JavaScript 代码，那就太棒了。如果是 ES6 生成器代码，那就更好了!我的谷歌搜索功能快用完了。
下面是带有几个 Jasmine 测试的代码片段:
function getPossibleGroupCombinations() {
return [];
}
describe('getPossibleGroupCombinations', () => {
it('works with a tiny set', () => {
const possibleCombos = getPossibleGroupCombinations(['a', 'b', 'c'], [2, 1]);
expect(possibleCombos).toEqual([
[['a', 'b'], ['c']],
[['a', 'c'], ['b']],
[['b', 'c'], ['a']],
]);
});
it('works with a big set', () => {
const possibleCombos = getPossibleGroupCombinations(
['a', 'b', 'c', 'd', 'e', 'f', 'g'],
[3, 2, 2]
);
expect(possibleCombos).toEqual([
[['a', 'b', 'c'], ['d', 'e'], ['f', 'g']],
[['a', 'b', 'c'], ['d', 'f'], ['e', 'g']],
[['a', 'b', 'c'], ['d', 'g'], ['e', 'f']],
[['a', 'b', 'c'], ['e', 'f'], ['d', 'g']],
[['a', 'b', 'c'], ['e', 'g'], ['d', 'f']],
[['a', 'b', 'c'], ['f', 'g'], ['d', 'e']],
[['a', 'b', 'd'], ['c', 'e'], ['f', 'g']],
[['a', 'b', 'd'], ['c', 'f'], ['e', 'g']],
[['a', 'b', 'd'], ['c', 'g'], ['e', 'f']],
[['a', 'b', 'd'], ['e', 'f'], ['c', 'g']],
[['a', 'b', 'd'], ['e', 'g'], ['c', 'f']],
[['a', 'b', 'd'], ['f', 'g'], ['c', 'e']],
[['a', 'b', 'e'], ['c', 'd'], ['f', 'g']],
[['a', 'b', 'e'], ['c', 'f'], ['d', 'g']],
[['a', 'b', 'e'], ['c', 'g'], ['d', 'f']],
[['a', 'b', 'e'], ['d', 'f'], ['c', 'g']],
[['a', 'b', 'e'], ['d', 'g'], ['c', 'f']],
[['a', 'b', 'e'], ['f', 'g'], ['c', 'd']],
[['a', 'b', 'f'], ['c', 'd'], ['e', 'g']],
[['a', 'b', 'f'], ['c', 'e'], ['d', 'g']],
[['a', 'b', 'f'], ['c', 'g'], ['d', 'e']],
[['a', 'b', 'f'], ['d', 'e'], ['c', 'g']],
[['a', 'b', 'f'], ['d', 'g'], ['c', 'e']],
[['a', 'b', 'f'], ['e', 'g'], ['c', 'd']],
[['a', 'b', 'g'], ['c', 'd'], ['e', 'f']],
[['a', 'b', 'g'], ['c', 'e'], ['d', 'f']],
[['a', 'b', 'g'], ['c', 'f'], ['d', 'e']],
[['a', 'b', 'g'], ['d', 'e'], ['c', 'f']],
[['a', 'b', 'g'], ['d', 'f'], ['c', 'e']],
[['a', 'b', 'g'], ['e', 'f'], ['c', 'd']],
[['a', 'c', 'd'], ['b', 'e'], ['f', 'g']],
[['a', 'c', 'd'], ['b', 'f'], ['e', 'g']],
[['a', 'c', 'd'], ['b', 'g'], ['e', 'f']],
[['a', 'c', 'd'], ['e', 'f'], ['b', 'g']],
[['a', 'c', 'd'], ['e', 'g'], ['b', 'f']],
[['a', 'c', 'd'], ['f', 'g'], ['b', 'e']],
[['a', 'c', 'e'], ['b', 'd'], ['f', 'g']],
[['a', 'c', 'e'], ['b', 'f'], ['d', 'g']],
[['a', 'c', 'e'], ['b', 'g'], ['d', 'f']],
[['a', 'c', 'e'], ['d', 'f'], ['b', 'g']],
[['a', 'c', 'e'], ['d', 'g'], ['b', 'f']],
[['a', 'c', 'e'], ['f', 'g'], ['b', 'd']],
[['a', 'c', 'f'], ['b', 'd'], ['e', 'g']],
[['a', 'c', 'f'], ['b', 'e'], ['d', 'g']],
[['a', 'c', 'f'], ['b', 'g'], ['d', 'e']],
[['a', 'c', 'f'], ['d', 'e'], ['b', 'g']],
[['a', 'c', 'f'], ['d', 'g'], ['b', 'e']],
[['a', 'c', 'f'], ['e', 'g'], ['b', 'd']],
[['a', 'c', 'g'], ['b', 'd'], ['e', 'f']],
[['a', 'c', 'g'], ['b', 'e'], ['d', 'f']],
[['a', 'c', 'g'], ['b', 'f'], ['d', 'e']],
[['a', 'c', 'g'], ['d', 'e'], ['b', 'f']],
[['a', 'c', 'g'], ['d', 'f'], ['b', 'e']],
[['a', 'c', 'g'], ['e', 'f'], ['b', 'd']],
[['a', 'd', 'e'], ['b', 'c'], ['f', 'g']],
[['a', 'd', 'e'], ['b', 'f'], ['c', 'g']],
[['a', 'd', 'e'], ['b', 'g'], ['c', 'f']],
[['a', 'd', 'e'], ['c', 'f'], ['b', 'g']],
[['a', 'd', 'e'], ['c', 'g'], ['b', 'f']],
[['a', 'd', 'e'], ['f', 'g'], ['b', 'c']],
[['a', 'd', 'f'], ['b', 'c'], ['e', 'g']],
[['a', 'd', 'f'], ['b', 'e'], ['c', 'g']],
[['a', 'd', 'f'], ['b', 'g'], ['c', 'e']],
[['a', 'd', 'f'], ['c', 'e'], ['b', 'g']],
[['a', 'd', 'f'], ['c', 'g'], ['b', 'e']],
[['a', 'd', 'f'], ['e', 'g'], ['b', 'c']],
[['a', 'd', 'g'], ['b', 'c'], ['e', 'f']],
[['a', 'd', 'g'], ['b', 'e'], ['c', 'f']],
[['a', 'd', 'g'], ['b', 'f'], ['c', 'e']],
[['a', 'd', 'g'], ['c', 'e'], ['b', 'f']],
[['a', 'd', 'g'], ['c', 'f'], ['b', 'e']],
[['a', 'd', 'g'], ['e', 'f'], ['b', 'c']],
[['a', 'e', 'f'], ['b', 'c'], ['d', 'g']],
[['a', 'e', 'f'], ['b', 'd'], ['c', 'g']],
[['a', 'e', 'f'], ['b', 'g'], ['c', 'd']],
[['a', 'e', 'f'], ['c', 'd'], ['b', 'g']],
[['a', 'e', 'f'], ['c', 'g'], ['b', 'd']],
[['a', 'e', 'f'], ['d', 'g'], ['b', 'c']],
[['a', 'e', 'g'], ['b', 'c'], ['d', 'f']],
[['a', 'e', 'g'], ['b', 'd'], ['c', 'f']],
[['a', 'e', 'g'], ['b', 'f'], ['c', 'd']],
[['a', 'e', 'g'], ['c', 'd'], ['b', 'f']],
[['a', 'e', 'g'], ['c', 'f'], ['b', 'd']],
[['a', 'e', 'g'], ['d', 'f'], ['b', 'c']],
[['a', 'f', 'g'], ['b', 'c'], ['d', 'e']],
[['a', 'f', 'g'], ['b', 'd'], ['c', 'e']],
[['a', 'f', 'g'], ['b', 'e'], ['c', 'd']],
[['a', 'f', 'g'], ['c', 'd'], ['b', 'e']],
[['a', 'f', 'g'], ['c', 'e'], ['b', 'd']],
[['a', 'f', 'g'], ['d', 'e'], ['b', 'c']],
[['b', 'c', 'd'], ['a', 'e'], ['f', 'g']],
[['b', 'c', 'd'], ['a', 'f'], ['e', 'g']],
[['b', 'c', 'd'], ['a', 'g'], ['e', 'f']],
[['b', 'c', 'd'], ['e', 'f'], ['a', 'g']],
[['b', 'c', 'd'], ['e', 'g'], ['a', 'f']],
[['b', 'c', 'd'], ['f', 'g'], ['a', 'e']],
[['b', 'c', 'e'], ['a', 'd'], ['f', 'g']],
[['b', 'c', 'e'], ['a', 'f'], ['d', 'g']],
[['b', 'c', 'e'], ['a', 'g'], ['d', 'f']],
[['b', 'c', 'e'], ['d', 'f'], ['a', 'g']],
[['b', 'c', 'e'], ['d', 'g'], ['a', 'f']],
[['b', 'c', 'e'], ['f', 'g'], ['a', 'd']],
[['b', 'c', 'f'], ['a', 'd'], ['e', 'g']],
[['b', 'c', 'f'], ['a', 'e'], ['d', 'g']],
[['b', 'c', 'f'], ['a', 'g'], ['d', 'e']],
[['b', 'c', 'f'], ['d', 'e'], ['a', 'g']],
[['b', 'c', 'f'], ['d', 'g'], ['a', 'e']],
[['b', 'c', 'f'], ['e', 'g'], ['a', 'd']],
[['b', 'c', 'g'], ['a', 'd'], ['e', 'f']],
[['b', 'c', 'g'], ['a', 'e'], ['d', 'f']],
[['b', 'c', 'g'], ['a', 'f'], ['d', 'e']],
[['b', 'c', 'g'], ['d', 'e'], ['a', 'f']],
[['b', 'c', 'g'], ['d', 'f'], ['a', 'e']],
[['b', 'c', 'g'], ['e', 'f'], ['a', 'd']],
[['b', 'd', 'e'], ['a', 'c'], ['f', 'g']],
[['b', 'd', 'e'], ['a', 'f'], ['c', 'g']],
[['b', 'd', 'e'], ['a', 'g'], ['c', 'f']],
[['b', 'd', 'e'], ['c', 'f'], ['a', 'g']],
[['b', 'd', 'e'], ['c', 'g'], ['a', 'f']],
[['b', 'd', 'e'], ['f', 'g'], ['a', 'c']],
[['b', 'd', 'f'], ['a', 'c'], ['e', 'g']],
[['b', 'd', 'f'], ['a', 'e'], ['c', 'g']],
[['b', 'd', 'f'], ['a', 'g'], ['c', 'e']],
[['b', 'd', 'f'], ['c', 'e'], ['a', 'g']],
[['b', 'd', 'f'], ['c', 'g'], ['a', 'e']],
[['b', 'd', 'f'], ['e', 'g'], ['a', 'c']],
[['b', 'd', 'g'], ['a', 'c'], ['e', 'f']],
[['b', 'd', 'g'], ['a', 'e'], ['c', 'f']],
[['b', 'd', 'g'], ['a', 'f'], ['c', 'e']],
[['b', 'd', 'g'], ['c', 'e'], ['a', 'f']],
[['b', 'd', 'g'], ['c', 'f'], ['a', 'e']],
[['b', 'd', 'g'], ['e', 'f'], ['a', 'c']],
[['b', 'e', 'f'], ['a', 'c'], ['d', 'g']],
[['b', 'e', 'f'], ['a', 'd'], ['c', 'g']],
[['b', 'e', 'f'], ['a', 'g'], ['c', 'd']],
[['b', 'e', 'f'], ['c', 'd'], ['a', 'g']],
[['b', 'e', 'f'], ['c', 'g'], ['a', 'd']],
[['b', 'e', 'f'], ['d', 'g'], ['a', 'c']],
[['b', 'e', 'g'], ['a', 'c'], ['d', 'f']],
[['b', 'e', 'g'], ['a', 'd'], ['c', 'f']],
[['b', 'e', 'g'], ['a', 'f'], ['c', 'd']],
[['b', 'e', 'g'], ['c', 'd'], ['a', 'f']],
[['b', 'e', 'g'], ['c', 'f'], ['a', 'd']],
[['b', 'e', 'g'], ['d', 'f'], ['a', 'c']],
[['b', 'f', 'g'], ['a', 'c'], ['d', 'e']],
[['b', 'f', 'g'], ['a', 'd'], ['c', 'e']],
[['b', 'f', 'g'], ['a', 'e'], ['c', 'd']],
[['b', 'f', 'g'], ['c', 'd'], ['a', 'e']],
[['b', 'f', 'g'], ['c', 'e'], ['a', 'd']],
[['b', 'f', 'g'], ['d', 'e'], ['a', 'c']],
[['c', 'd', 'e'], ['a', 'b'], ['f', 'g']],
[['c', 'd', 'e'], ['a', 'f'], ['b', 'g']],
[['c', 'd', 'e'], ['a', 'g'], ['b', 'f']],
[['c', 'd', 'e'], ['b', 'f'], ['a', 'g']],
[['c', 'd', 'e'], ['b', 'g'], ['a', 'f']],
[['c', 'd', 'e'], ['f', 'g'], ['a', 'b']],
[['c', 'd', 'f'], ['a', 'b'], ['e', 'g']],
[['c', 'd', 'f'], ['a', 'e'], ['b', 'g']],
[['c', 'd', 'f'], ['a', 'g'], ['b', 'e']],
[['c', 'd', 'f'], ['b', 'e'], ['a', 'g']],
[['c', 'd', 'f'], ['b', 'g'], ['a', 'e']],
[['c', 'd', 'f'], ['e', 'g'], ['a', 'b']],
[['c', 'd', 'g'], ['a', 'b'], ['e', 'f']],
[['c', 'd', 'g'], ['a', 'e'], ['b', 'f']],
[['c', 'd', 'g'], ['a', 'f'], ['b', 'e']],
[['c', 'd', 'g'], ['b', 'e'], ['a', 'f']],
[['c', 'd', 'g'], ['b', 'f'], ['a', 'e']],
[['c', 'd', 'g'], ['e', 'f'], ['a', 'b']],
[['c', 'e', 'f'], ['a', 'b'], ['d', 'g']],
[['c', 'e', 'f'], ['a', 'd'], ['b', 'g']],
[['c', 'e', 'f'], ['a', 'g'], ['b', 'd']],
[['c', 'e', 'f'], ['b', 'd'], ['a', 'g']],
[['c', 'e', 'f'], ['b', 'g'], ['a', 'd']],
[['c', 'e', 'f'], ['d', 'g'], ['a', 'b']],
[['c', 'e', 'g'], ['a', 'b'], ['d', 'f']],
[['c', 'e', 'g'], ['a', 'd'], ['b', 'f']],
[['c', 'e', 'g'], ['a', 'f'], ['b', 'd']],
[['c', 'e', 'g'], ['b', 'd'], ['a', 'f']],
[['c', 'e', 'g'], ['b', 'f'], ['a', 'd']],
[['c', 'e', 'g'], ['d', 'f'], ['a', 'b']],
[['c', 'f', 'g'], ['a', 'b'], ['d', 'e']],
[['c', 'f', 'g'], ['a', 'd'], ['b', 'e']],
[['c', 'f', 'g'], ['a', 'e'], ['b', 'd']],
[['c', 'f', 'g'], ['b', 'd'], ['a', 'e']],
[['c', 'f', 'g'], ['b', 'e'], ['a', 'd']],
[['c', 'f', 'g'], ['d', 'e'], ['a', 'b']],
[['d', 'e', 'f'], ['a', 'b'], ['c', 'g']],
[['d', 'e', 'f'], ['a', 'c'], ['b', 'g']],
[['d', 'e', 'f'], ['a', 'g'], ['b', 'c']],
[['d', 'e', 'f'], ['b', 'c'], ['a', 'g']],
[['d', 'e', 'f'], ['b', 'g'], ['a', 'c']],
[['d', 'e', 'f'], ['c', 'g'], ['a', 'b']],
[['d', 'e', 'g'], ['a', 'b'], ['c', 'f']],
[['d', 'e', 'g'], ['a', 'c'], ['b', 'f']],
[['d', 'e', 'g'], ['a', 'f'], ['b', 'c']],
[['d', 'e', 'g'], ['b', 'c'], ['a', 'f']],
[['d', 'e', 'g'], ['b', 'f'], ['a', 'c']],
[['d', 'e', 'g'], ['c', 'f'], ['a', 'b']],
[['d', 'f', 'g'], ['a', 'b'], ['c', 'e']],
[['d', 'f', 'g'], ['a', 'c'], ['b', 'e']],
[['d', 'f', 'g'], ['a', 'e'], ['b', 'c']],
[['d', 'f', 'g'], ['b', 'c'], ['a', 'e']],
[['d', 'f', 'g'], ['b', 'e'], ['a', 'c']],
[['d', 'f', 'g'], ['c', 'e'], ['a', 'b']],
[['e', 'f', 'g'], ['a', 'b'], ['c', 'd']],
[['e', 'f', 'g'], ['a', 'c'], ['b', 'd']],
[['e', 'f', 'g'], ['a', 'd'], ['b', 'c']],
[['e', 'f', 'g'], ['b', 'c'], ['a', 'd']],
[['e', 'f', 'g'], ['b', 'd'], ['a', 'c']],
[['e', 'f', 'g'], ['c', 'd'], ['a', 'b']],
]);
});
});
// load jasmine htmlReporter
(function() {
var env = jasmine.getEnv();
env.addReporter(new jasmine.HtmlReporter());
env.execute();
}());<link href="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.css" rel="stylesheet"/>
<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.js"></script>
<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine-html.js"></script>最佳答案
概念证明......
您可以使用数组长度的阶乘来获得所需的排列。
基本上，该算法计算数组的索引并重新组合结果。
subsets 数组只是装饰性的。
这种方法很慢，因为它会生成第 nth 个排列。一种更快的方法可能是继续上一个排列并继续下一个排列。
function getN(n, array, subsets) {
var f,
l = array.length,
indices = [],
temp;
array = array.slice();
while (l--) {
f = factorial(l);
indices.push(Math.floor(n / f));
n %= f;
}
temp = indices.map(i => array.splice(i, 1)[0]);
return subsets
? subsets.map((i => l => temp.slice(i, i += l))(0))
: temp;
}
function factorial(num) {
var result = 1;
while (num) {
result *= num;
num--;
}
return result;
}
var i, l,
array = ['a', 'b', 'c', 'd', 'e', 'f', 'g'],
subsets = [3, 2, 2],
pre = document.getElementById('out');
for (i = 0, l = factorial(array.length); i < l; i++) {
pre.innerHTML += i.toString().padStart(4) +': ' + JSON.stringify(getN(i, array, subsets)) + '\n';
}<pre id="out"></pre>关于javascript - 生成集合的所有可能的分组/子集组合，用完每个项目，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52525394/