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

Question

我有一个对象数组,例如

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"}, {"a": "nm"}, {"ab": "i"}],
    [{"a": "x"}, {"a": "nm"}, {"ab": "4"}]
];

我没有找到实现所需结果的方法(假设input.length可能远大于2或3 - 甚至15-20可能还不够)没有因子级别的计算量,这在物理上是不可能的.有没有办法有一些合理的性能来解决这样的问题？
重要提示:是的,显然,对于相对较大的数值,input.length理论上可能会有非常多的可能组合,但在实践中,result.length总是相当小(可能是100-200,我甚至怀疑它可能达到1000. ..).但为了安全起见,我想设置一些限制(比如1000),这样一旦result.length达到这个限制,该功能就会返回电流result并停止.

Answer 1

看到这个问题，有点像笛卡尔积。事实上，如果在操作之前，对数据模型进行一些修改，那么在几乎所有情况下，预期结果都是笛卡尔积。但是，有一种情况（您提供的第二个示例）需要特殊处理。这就是我所做的：

1. 稍微调整一下模型数据（这只会完成一次），以获得适合应用笛卡尔积的东西。
2. 处理具有多个请求相同字符串的参数的“特殊情况”。

所有重要的逻辑都在 内cartessianProdModified。代码中的重要部分都已注释。希望它能帮助您解决问题或至少为您提供一些想法。

这是一个小提琴，这是代码：

var arr = [
    {"a": "x"},
    {"b": "0"},
    {"c": "k"},
    {"a": "nm"},
    {"b": "765"},
    {"ab": "i"},
    {"bc": "x"},
    {"ab": "4"},
    {"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, val, 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, val, {})] : processedObj[key].reduce(function (memo, val) {
        return memo.concat(set(key, val, {}));
    }, []);
}

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