没有重复的笛卡尔乘积
Cartesian product without duplicates
本文关键字:笛卡尔 更新时间:2023-09-26
我正在使用一个笛卡尔乘积函数,给定[1], [1,2,3], [1,2,3]
返回 9 种组合:
[ [ 1, 1, 1 ],
[ 1, 2, 1 ],
[ 1, 3, 1 ],
[ 1, 1, 2 ],
[ 1, 2, 2 ],
[ 1, 3, 2 ],
[ 1, 1, 3 ],
[ 1, 2, 3 ],
[ 1, 3, 3 ] ]
但是无论顺序如何,我都需要删除具有相同项目的那些,因此[ 1, 3, 1 ]
和[ 1, 1, 3 ]
对我来说是一样的。结果应包含 6 项:
[ [ 1, 1, 1 ],
[ 1, 2, 1 ],
[ 1, 3, 1 ],
[ 1, 2, 2 ],
[ 1, 3, 2 ],
[ 1, 3, 3 ] ]
我可以编写一个函数来比较所有可能的对与_.xor
,但对于较大的数字,它可能效率非常低。Javascript中有什么好方法可以做到这一点吗?一种有效的方法来比较所有可能的对或没有重复的笛卡尔乘积的算法?
对笛卡尔积的每个数组进行排序
[ 1, 2, 1 ] -> [1 , 1 , 2]
[ 1, 1, 2 ] -> [1 , 1 , 2]
然后将这些排序的数组收集到一个集合中,这将删除重复项。
当然,你可以在构造笛卡尔积时而不是之后这样做。
JavaScript
有 Set 和 Map,但是它们通过引用而不是值来比较对象和数组,因此您无法直接利用它。这个想法是使用一个键函数,该函数在将项目放入集合之前对项目进行排序和 json 编码。
纯 ES5:
function product(sets) {
if (sets.length > 0) {
var head = sets[0];
var tail = product(sets.slice(1));
var result = [];
head.forEach(function(x) {
tail.forEach(function(xs) {
var item = xs.slice(0);
item.unshift(x);
result.push(item);
});
});
return result;
} else {
return [[]];
}
}
function myKeyFn(item) {
return JSON.stringify(item.slice(0).sort());
}
function uniqBy(items, keyFn) {
var hasOwn = Object.prototype.hasOwnProperty, keyset = {};
return items.filter(function(item) {
var key = keyFn(item);
if (hasOwn.call(keyset, key)) {
return false;
} else {
keyset[key] = 1;
return true;
}
});
}
function uniqProduct(sets) {
return uniqBy(product(sets), myKeyFn);
}
function log(x) {
console.log(x);
var pre = document.createElement('pre');
pre.appendChild(document.createTextNode(x));
document.body.appendChild(pre);
}
log(uniqProduct([[1],[1,2,3],[1,2,3]]).map(JSON.stringify).join("'n"));
<pre></pre>
lodash + modern JavaScript:
// Note: This doesn't compile on current babel.io/repl due to a bug
function product(sets) {
if (sets.length > 0) {
const [x, ...xs] = sets;
const products = product(xs);
return _.flatMap(x, head => products.map(tail => [head, ...tail]));
} else {
return [[]];
}
}
function uniqProduct(sets) {
return _.uniqBy(product(sets), x => JSON.stringify(x.slice(0).sort()));
}
console.log(uniqProduct([[1],[1,2,3],[1,2,3]]).map(JSON.stringify).join("'n"));
JavaScript设置了数据结构。
因此,将结果存储在一个集合中,其中集合的每个元素都是原始集合中的数字对以及该数字出现的次数的集合。
因此,您的结果将如下所示:
[
{1:3},
{1:2, 2: 1},
{ 1:2, 3:1},
{ 1:1, 2:2},
{ 1:1, 2:1, 3:1},
{ 1:1, 3:2 } ]
这样,您将无法再次将对象添加到集合中。
相关文章:
- 通过js在新选项卡中有条件地打开url
- 多维数组的笛卡尔乘积
- 没有重复的笛卡尔乘积
- 笛卡尔乘积的反转
- 计算 1 个数组中元素的笛卡尔乘积
- 卡鲁弗雷德塞尔将类添加到活动幻灯片
- 通过循环访问未知数量的数组来创建JavaScript对象的笛卡尔乘积(powerset?)
- 拉斐尔SVG路径的一部分卡在原地
- 如何调整卡鲁弗雷德塞尔滑块的上边距
- 2 个数组的笛卡尔积
- javascript中对象的笛卡尔乘积
- 如何将两个数组组合为笛卡尔积
- 如何使用科学记数法使(笛卡尔)图表轴按比例缩放
- [Javascript]获取所有数组组合(笛卡尔乘积)
- 如何在javascript中实现不同长度n数组的笛卡尔乘积
- 在javascript中获取最近的笛卡尔轴对齐矢量
- 实现卡尔曼滤波器以平滑来自 deviceOriented API 的数据
- 极坐标到笛卡尔坐标的函数没有输出正确的数据
- 英特尔XDK保存pdf到存储卡文件传输.下载- android
- 笛卡尔坐标与球坐标的转换