比方说，我们有这样的阵列：myArray的= [A，A，B，B，C，C，d，E]
我想创建一个算法，以便它会发现所有的加起来整个阵列，在那里重复没有任何元素的组合。
示例性的组合：
[A, B, C, D, E] [A, B, C]
[A, B, C, D] [A, B, C, E]
[A, B, C] [A, B, C] [D, E]
澄清：[A, B, C] [A, B, C] [D, E]和[A, B, C] [D, E] [A, B, C]是相同的组合。另外随着子集的顺序没有关系为好。例如[A,B,C]和[B,A,C]应该是相同的。到目前为止，我没有超越进步
var myArray = ["A", "A", "B", "B", "C", "C", "D", "E"]
console.log([...new Set(myArray)])但是，这并不能帮助所有，它只是返回一个不同的组。我找不到以前发布过类似的问题，所以任何人都可以指导我在这里如何实现这一目标？
我得到315种组合。那正确吗？ :)
这里有一个递归：
function distribute(e, i, _comb){
// No more e's
if (e[1] == 0)
return [_comb];
// We're beyond the combination
if (i == -1)
return [_comb.concat([e])];
let result = [];
for (let c=1; c<=Math.min(_comb[i][1], e[1]); c++){
let comb = _comb.map(x => x.slice());
if (c == comb[i][1]){
comb[i][0] += e[0];
} else {
comb[i][1] -= c;
comb.push([comb[i][0] + e[0], c]);
}
result = result.concat(distribute([e[0], e[1] - c], i - 1, comb));
}
let comb = _comb.map(x => x.slice());
return result.concat(distribute(e, i - 1, comb));
}
function f(arr){
function g(i){
if (i == 0)
return [[arr[0]]];
const combs = g(i - 1);
let result = [];
for (let comb of combs)
result = result.concat(
distribute(arr[i], comb.length - 1, comb));
return result;
}
return g(arr.length - 1);
}
function show(arr){
const rs = f(arr);
const set = new Set();
for (let r of rs){
const _r = JSON.stringify(r);
if (set.has(_r))
console.log('Duplicate: ' + _r);
set.add(_r);
}
let str = '';
for (let r of set)
str += '\n' + r
str += '\n\n';
console.log(JSON.stringify(arr));
console.log(set.size + ' combinations:');
console.log(str);
}
show([['A', 2], ['B', 2], ['C', 2], ['D', 1], ['E', 1]]);你可以通过枚举所有可能的组合，然后找到permutatinos对每个组合做，然后过滤元件，以确保它们是唯一的。这种过滤可以通过插入到一组来完成。
所述子集的功能是从@le_m（Check this answer）。
function* subsets(array, offset = 0) {
while (offset < array.length) {
let first = array[offset++];
for (let subset of subsets(array, offset)) {
subset.push(first);
yield subset;
}
}
yield [];
}
function* permutations(elements) {
if (elements.length === 1) {
yield elements;
} else {
let [first, ...rest] = elements;
for (let perm of permutations(rest)) {
for (let i = 0; i < elements.length; i++) {
let start = perm.slice(0, i);
let rest = perm.slice(i);
yield [...start, first, ...rest];
}
}
}
}
const arr = ['A', 'a', 'B', 'b', 'C', 'c', 'd', 'e'];
const results = new Set();
for (let subset of subsets(arr)) {
if (subset.length) {
for (let permut of permutations(subset)) {
results.add(permut.join(''));
}
}
}
console.log([...results]);这会产生想要的结果的所有可能的排列，所以也没有回答这个问题。
function* combinations(combos) {
yield combos;
for(const [i1, group] of combos.entries()) {
for(const [i2, group2] of combos.slice(i1 + 1).entries()) {
if(group.some(v => group2.includes(v))) continue;
yield* combinations([
...combos.filter((_, index) => index !== i1 && index !== i2),
[...group, ...group2]
]);
}
}
}
console.log([...combinations([1, 2, 3, 4, 1].map(v => ([v])))]);
你可以用只含有一个元素组合的数组开始，然后对这些组合和合并他们的两个数组，进行递归。
你可以第一组相同的元素并计数，造成这样的表：
1 | 2 | 3 | 4
1 | | 3 | 4
1
（1被复制两次，3和4次）
现在，你可以开始，在第一个四个要素出来，那么3在第二排，然后一个导致在最后一排
[[1, 2, 3, 4], [1, 3, 4], [1]]
我们获得下一个组合，只是把3出从第一行，并让其他值向上移动：
1 | | 3 | 4
1 | | | 4
现在又取出行，你会得到
[[1, 2, 3], [1, 3, 4], [1, 4]]
现在，重复这种模式从第一行（坐2，1）等，也重复与行，那么你应该得到你想要达到的效果。
const counts = new Map;
for(const value of [1, 1, 1, 2, 3, 3, 4, 4])
counts.set(value, (counts.get(value) || 0) + 1);
const result = [];
for(let combo = 0; combo < counts.size; combo++) {
const subResult = [];
const combos = [...counts];
for(let i = 0; i <= combo; i++) combos[i][0] -= 1;
subResult.push(combos.slice(0, combo).map(([_, value]) => value);
while(combos.some(([count]) => count > 0)) {
subResult.push(combos.filter(([count]) => count > 0).map(([_, value] => value));
}
result.push(subResult);
}
实现从无到有，一个算法：
const decrementKey = (o, k) => o[k]--;
const isEmpty = (o) => Object.keys(o).length === 0;
const removeKeys = (o) => Object.keys(o).forEach(k => { if (o[k] < 1) delete o[k]; });
const frequencyMap = (a) => a.reduce((r, v) => Object.assign(r, { [v] : (r[v] || 0) + 1 }), {});
const cloneMap = (o) => Object.keys(o).reduce((r, k) => Object.assign(r, { [k] : o[k] }), {});
let myArray = ["A", "A", "B", "B", "C", "C", "D", "E"];
let groups = solve(myArray);
console.log(groups.map(g => g.map(a => a.join('')).join(' | ')).join('\n'));
function solve(arr) {
let freq = frequencyMap(arr), results = [];
for (let max = Object.keys(freq).length; max > 1; max--) {
let result = [], clone = cloneMap(freq);
while (!isEmpty(clone)) {
result.push(Object.keys(clone).reduce((res, key, index) => {
if (index < max) {
decrementKey(clone, key);
res.push(key);
}
return res;
}, []));
removeKeys(clone);
}
if (result.length > 0) results.push(result);
}
return results;
}.as-console-wrapper { top: 0; max-height: 100% !important; }