数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装研究
法学研究如何在 JavaScript 中找到多重集的所有划分，其中每个部分的元素都不同
假设我们有这样一个数组：
const arr = [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] 应该被认为是相同的。
示例
代码如下：
const arr = [['A', 1], ['B', 2], ['C', 3]];
const spread = (arr, ind, combination) => {
if (arr[1] === 0)
return [combination];
if (ind === −1)
return [combination.concat([arr])];
let result = [];
for (let c=1; c<=Math.min(combination[ind][1], arr[1]); c++){
let comb = combination.map(x => x.slice());
if (c == comb[ind][1]){
comb[ind][0] += arr[0];
} else {
comb[ind][1] −= c;
comb.push([comb[ind][0] + arr[0], c]);
}
result = result.concat(spread([arr[0], arr[1] − c], ind − 1, comb));
}
let comb = combination.map(x => x.slice());
return result.concat(spread(arr, ind − 1, comb));
};
const helper = arr => {
function inner(ind){
if (ind === 0)
return [[arr[0]]];
const combs = inner(ind − 1);
let result = [];
for (let comb of combs)
result = result.concat(
spread(arr[ind], comb.length − 1, comb));
return result;
}
return inner(arr.length − 1);
};
const returnPattern = (arr = []) => {
const rs = helper(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 += '
' + r
str += '
';
return str;
};
console.log(returnPattern(arr));输出
控制台输出：
[["ABC",1],["BC",1],["C",1]] [["AB",1],["BC",1],["C",2]] [["ABC",1],["B",1],["C",2]] [["AB",1],["B",1],["C",3]] [["AC",1],["B",1],["BC",1],["C",1]] [["A",1],["B",1],["BC",1],["C",2]] [["AC",1],["BC",2]] [["A",1],["BC",2],["C",1]] [["AC",1],["B",2],["C",2]] [["A",1],["B",2],["C",3]]
更新于：2020年11月21日
147 次浏览
广告