我有一组对象,例如
var arr = [
{"a": "x"},{"b": "0"},{"c": "k"},{"a": "nm"},{"b": "765"},{"ab": "i"},{"bc": "x"},{"ab": "4"},{"abc": "L"}
];
假设我只对其键对应于var input = [“ab”,“bc”]的对象感兴趣.这意味着我想以下列方式使用result [i] .length == 2提取所有可能的子数组：
var result = [
[{"ab": "i"},{"bc": "x"}],[{"ab": "4"},{"bc": "x"}] // or [{"bc": "x"},{"ab": "4"}]
];
– 也就是说,子数组中对象的顺序绝对不重要：我只对每个子数组包含两个对象 – {“ab”：…}和{“bc”：…}这一事实感兴趣.
如果我对var input = [“a”,“a”,“ab”]感兴趣,结果应如下所示：
var result = [
[{"a": "x"},{"ab": "i"}],[{"a": "x"},{"ab": "4"}]
];
我无法找到实现所需结果的方法(假设input.length可能远大于2或3 – 甚至15-20可能还不够)没有因子级别的计算量,这在物理上是不可能的.有没有办法在解决这样的问题时有一些合理的表现？
重要说明：是的,显然,对于相对较大的input.length值,理论上可能有非常大量的可能组合,但实际上,result.length总是相当小(可能是100-200,我甚至怀疑)它可以达到1000 …).但为了安全起见,我想设置一些限制(比如1000),这样只要result.length达到这个限制,该函数就会返回当前结果并停止.
解决方法
看到问题,它看起来像一个卡西斯产品.实际上,如果在操作之前,数据模型稍微修改了一下,那么在几乎所有情况下,预期结果都是卡西斯产品.但是,有一个案例(你提供的第二个例子)需要特殊处理.这是我做的：
>稍微调整模型数据(这将只进行一次),以便有适合应用cartessian产品的东西.
>处理具有多个请求相同字符串的参数的“特殊情况”.
所有重要的逻辑都在cartessianProdModified中.代码中的重要位被注释.希望它可以帮助您解决问题或至少给您一些想法.
这是一个fiddle,这是代码：
var arr = [
{"a": "x"},{"abc": "L"},{"dummy": "asdf"}
];
// Utility function to be used in the cartessian product
function flatten(arr) {
return arr.reduce(function (memo,el) {
return memo.concat(el);
},[]);
}
// Utility function to be used in the cartessian product
function unique(arr) {
return Object.keys(arr.reduce(function (memo,el) {
return (memo[el] = 1) && memo;
},{}));
}
// It'll prepare the output in the expected way
function getobjArr(key,val,processedobj) {
var set = function (key,obj) {
return (obj[key] = val) && obj;
};
// The cartessian product is over so we can put the 'special case' in an object form so that we can get the expected output.
return val !== 'repeated' ? [set(key,{})] : processedobj[key].reduce(function (memo,val) {
return memo.concat(set(key,{}));
},[]);
}
// This is the main function. It'll make the cartessian product.
var cartessianProdModified = (function (arr) {
// Tweak the data model in order to have a set (key: array of values)
var processedobj = arr.reduce(function (memo,obj) {
var firstKey = Object.keys(obj)[0];
return (memo[firstKey] = (memo[firstKey] || []).concat(obj[firstKey])) && memo;
},{});
// Return a function that will perform the cartessian product of the args.
return function (args) {
// Spot repeated args.
var countArgs = args.reduce(function (memo,el) {
return (memo[el] = (memo[el] || 0) + 1) && memo;
},{}),// Remove repeated args so that the cartessian product works properly and more efficiently.
uniqArgs = unique(args);
return uniqArgs
.reduce(function (memo,el) {
return flatten(memo.map(function (x) {
// Special case: the arg is repeated: we have to treat as a unique value in order to do the cartessian product properly
return (countArgs[el] > 1 ? ['repeated'] : processedobj[el]).map(function (y) {
return x.concat(getobjArr(el,y,processedobj));
});
}));
},[[]]);
};
})(arr);
console.log(cartessianProdModified(['a','a','ab']));