How to extract all possible matching arrays of objects from one array of objects?

Question

I have an array of objects, e.g.

var arr = [
    {"a": "x"},
    {"b": "0"},
    {"c": "k"},
    {"a": "nm"},
    {"b": "765"},
    {"ab": "i"},
    {"bc": "x"},
    {"ab": "4"},
    {"abc": "L"}
];

Let's say I am only interested in objects whose keys correspond to var input = ["ab", "bc"]. It means that I want to extract all possible subarrays with result[i].length == 2 in the following way:

var result = [
    [{"ab": "i"}, {"bc": "x"}],
    [{"ab": "4"}, {"bc": "x"}] // or [{"bc": "x"}, {"ab": "4"}]
];

— that is, the order of objects in subarrays is absolutely not important: I am only interested in the fact that each subarray contains two objects — {"ab": ...} and {"bc": ...}.

If I was interested in var input = ["a","a","ab"], the result should be like this:

var result = [
    [{"a": "x"}, {"a": "nm"}, {"ab": "i"}],
    [{"a": "x"}, {"a": "nm"}, {"ab": "4"}]
];

I cannot find the way to achieve the desired result (assuming that input.length may be much greater than 2 or 3 — even 15–20 may be not enough) without factorial-level amount of computations, which is not physically possible. Is there a way to have some reasonable performance for solving such a problem?
Important note: yes, obviously, for relatively large values of input.length there theoretically may be possible to have very huge numbers of possible combinations, but in practice, result.length will always be reasonably small (maybe 100–200, I even doubt that it could reach 1000...). But for safety, I would want to just set some limit (say, 1000), such that as soon as result.length reaches this limit, the function just returns the current result and stops.

Answer 1

Seeing the problem, it kind of look like a cartessian product. In fact, if before operating, the data model is modified a bit, the expected result is, in almost all cases, a cartessian product. However, there's a case (the second example you provided) that needs special treatment. Here's what I did:

1. Tweak a bit the model data (this will be done only once) in order to have something suitable to apply cartessian product.
2. Treat the "special case" of having more than one parameter requesting the same string.

All the important logic is within cartessianProdModified. The important bits in the code are commented. Hope it helps you with your problem or at least gives you some ideas.

Here's a fiddle and here's the code:

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