javascript – 如何从一个对象数组中提取所有可能匹配的对象数组？

@H_301_0@

我有一组对象,例如

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']));

javascript – 如何从一个对象数组中提取所有可能匹配的对象数组？

解决方法

猜你在找的JavaScript相关文章