Как извлечь все возможные совпадающие массивы объектов из одного массива объектов?

Видя проблему, она выглядит как декартово произведение. На самом деле, если перед операцией немного изменить модель данных, ожидаемый результат почти во всех случаях будет декартовым произведением. Однако есть случай (второй приведенный вами пример), который требует особого отношения. Вот что я сделал:

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

Сортировка в алфавитном порядке arr и input, что равно O(nlogn), и если вы сможете сделать это при построении массивов, это может принести вам пользу.

Поясню свою мысль на примере:

var arr = [
    {"a": "x"},
    {"ab": "i"},
    {"ab": "4"},
    {"abc": "L"}
    {"bc": "x"},
];
var input = ["ab", "bc"];

Ищите input[0] в arr (линейно или даже с бинарным поиском для ускорения). Отметьте индекс.

Ищите input[1] в arr, но учитывайте только подмассив arr от индекса, отмеченного на предыдущем шаге, до его конца.

Если вы найдете все элементы input, переместите их в results (для этого вы можете сохранить временный объект).

Теперь нам нужно снова искать input[0], так как может случиться так, что две или более записей имеют общий ключ. Вы сохраните этот индекс, о котором я упоминал ранее, так что вы снова начнете поиск с этого индекса, и, поскольку arr отсортировано, вам придется проверять только следующий элемент и так далее.

Временная сложность:

Отсортируйте свои массивы (при условии, что вы не могли отсортировать их при их построении): O(nlogn), где n — количество элементов arr.

Двоичный поиск в arr для input[0]: O(logn)

Теперь следующий шаг поиска (для input[1]) намного меньше длины arr, поэтому очень пессимистичная граница будет O(n). На практике это, конечно, не будет O(n), и если вы хотите, вы также можете выполнить бинарный поиск для input[1], что будет стоить O(logm), где m — размер arr[index_stored: -1].

На этом этапе мы переходим к поиску следующего вхождения input[0], если оно есть, конечно, но поскольку мы сохранили индекс, мы точно знаем, с чего начать поиск, и нам нужно проверить только следующий элемент, это постоянная стоимость. , таким образом, O (1).

И затем мы делаем то же самое для input[1], как указано выше, что снова дешево.

Теперь все зависит от длины input, которая равна k, и кажется, что k < n, и сколько у вас есть вхождений ключа, верно?

Но при условии нормально-средней ситуации вся процедура имеет временную сложность:

O(nlogn)

Однако обратите внимание, что вам придется заплатить немного дополнительной памяти для хранения индексов, что зависит от количества вхождений ключа. С перебором aglrotihm, который был бы медленнее, вам не нужно было бы ничего дополнительно платить за память.

Возможно, не самый оптимальный способ. Я бы, вероятно, использовал какую-нибудь библиотеку для окончательного решения, но вот ряд шагов, которые сделают трюк для счастливого пути. Я добавлю немного комментариев в ближайшее время.

Создайте карту для одного ключа в исходном массиве (т.е. в каких индексах он виден, поскольку у нас может быть несколько записей)

   function getKeyMap( src, key ){
        var idx_arr = [];
        src.forEach(function(pair,idx){ if(Object.keys(pair)[0] === key){ idx_arr.push(idx)} });
        return idx_arr;
    }

И это сопоставление должно быть выполнено для всех ключей, которые вы хотите включить в фильтрацию.

function getKeysMap( src, keys ){
    var keys_map = [];
    keys.forEach(function(aKey){
        var aMap = getKeyMap(src,aKey);
        if( aMap.length ){
            keys_map.push(aMap);
        }

    });
    // if keys map lenght is less then keys length then you should throw an exception or something
    return keys_map;
}

Затем вы хотите построить все возможные комбинации. Я использую здесь рекурсию, возможно, не самым оптимальным способом.

function buildCombos( keys_map, carry, result ){
    if( keys_map.length === 0){
        result.push(carry);
        return;
    }
    var iter = keys_map.pop();
    iter.forEach(function(key){
        var cloneMap = keys_map.slice(0);
        var clone = carry.slice(0);
        clone.push(key);
        buildCombos(cloneMap, clone, result);
    });
}

Затем мне нужно отфильтровать результат, чтобы исключить двойные записи и записи с повторяющимися индексами.

function uniqueFilter(value, index, self) {
    return self.indexOf(value) === index;
}

function filterResult( map ){
    var filter = {};
    map.forEach(function(item){
        var unique = item.filter( uniqueFilter );
        if(unique.length === item.length){
            filter[unique.sort().join('')]=true;}
        });
    return filter;
}

А затем я просто декодирую полученную отфильтрованную карту в исходные данные

function decodeMap( map,src ){
    var result = [];
    Object.keys(map).forEach(function(item){
        var keys = item.split('');
        var obj = [];
        keys.forEach(function( j ){
            obj.push( src[j])
        });
        result.push(obj);
    });
    return result;
}

Обертка

function doItAll(arr, keys){
    // Get map of they keys in terms of numbers
    var maps = getKeysMap( arr, keys);
    // build combinations out of key map
    var combos = [];
    buildCombos(maps,[],combos);
    // filter results to get rid of same sequences and same indexes ina sequence
    var map = filterResult(combos);
    // decode map into the source array
    return decodeMap( map, arr )
}

Использование:

var res = doItAll(arr, ["a","a","ab"])

Если вы можете использовать функции ES6, вы можете использовать генераторы, чтобы не создавать большие промежуточные массивы. Казалось бы, вам нужен своего рода набор наборов со строками, содержащими только уникальные значения. Как уже упоминалось, вы можете подойти к этому, начав с декартова произведения объектов, соответствующих вашему input ключи:

'use strict';

function* product(...seqs) {
    const indices = seqs.map(() => 0),
          lengths = seqs.map(seq => seq.length);

    // A product of 0 is empty
    if (lengths.indexOf(0) != -1) {
        return;
    }

    while (true) {
        yield indices.map((i, iseq) => seqs[iseq][i]);
        // Update indices right-to-left
        let i;
        for (i = indices.length - 1; i >= 0; i--) {
            indices[i]++;
            if (indices[i] == lengths[i]) {
                // roll-over
                indices[i] = 0;
            } else {
                break;
            }
        }
        // If i is negative, then all indices have rolled-over
        if (i < 0) {
            break;
        }
    }
}

Генератор хранит индексы только между итерациями и генерирует новые строки по требованию. Чтобы на самом деле присоединиться к объектам, которые соответствуют вашим input ключам, вам сначала нужно, например, создать поиск:

function join(keys, values) {
    const lookup = [...new Set(keys)].reduce((o, k) => {
        o[k] = [];
        return o;
    }, {});

    // Iterate over array indices instead of objects them selves.
    // This makes producing unique rows later on a *lot* easier.
    for (let i of values.keys()) {
       const k = Object.keys(values[i])[0];
       if (lookup.hasOwnProperty(k)) {
           lookup[k].push(i);
       } 
    }

    return product(...keys.map(k => lookup[k]));
}

Затем вам нужно отфильтровать строки, содержащие повторяющиеся значения:

function isUniq(it, seen) {
    const notHadIt = !seen.has(it);
    if (notHadIt) {
        seen.add(it);
    }
    return notHadIt;
}

function* removeDups(iterable) {
    const seen = new Set();
    skip: for (let it of iterable) {
        seen.clear();
        for (let x of it) {
            if (!isUniq(x, seen)) {
                continue skip;
            }
        }
        yield it;
    }
}

А также глобально уникальные строки (аспект набора наборов):

function* distinct(iterable) {
    const seen = new Set();
    for (let it of iterable) {
        // Bit of a hack here, produce a known order for each row so
        // that we can produce a "set of sets" as output. Rows are
        // arrays of integers.
        const k = it.sort().join();
        if (isUniq(k, seen)) {
            yield it;
        }
    }
}

Чтобы связать все это:

function* query(input, arr) {
    for (let it of distinct(removeDups(join(input, arr)))) {
        // Objects from rows of indices
        yield it.map(i => arr[i]);
    }
}

function getResults(input, arr) {
    return Array.from(query(input, arr));
}

В действии:

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

console.log(getResults(["a", "a", "ab"], arr));
/*
[ [ { a: 'x' }, { a: 'nm' }, { ab: 'i' } ],
  [ { a: 'x' }, { a: 'nm' }, { ab: '4' } ] ]
*/

И обязательный jsFiddle.

Вы можете сделать это вручную с помощью циклов, но вы также можете использовать встроенные функции Array.prototype.filter() для фильтрации массива и Array.prototype.indexOf, чтобы проверить, находится ли элемент внутри другого массива:

var filtered = arr.filter(function(pair){
    return input.indexOf(Object.keys(pair)[0]) != -1;
});

Это дает вам массив только с объектами, которые соответствуют вашим критериям.

Теперь штука с массивом result на математическом языке называется "комбинациями". Это именно то, что вам нужно, поэтому я не буду описывать это здесь. Здесь приведен способ создания всех комбинаций массива (набора) - https://stackoverflow.com/a/18250883/3132718

// function assumes each element is array, so we need to wrap each one in an array 
for(var i in filtered) {
    filtered[i] = [filtered[i]];
}
var result = getCombinations(filtered, input.length /* how many elements in each sub-array (subset) */);

Object.keys(pair)[0] — это способ получить первый ключ объекта без повторения (https://stackoverflow.com/a/28670472)