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

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"}] 
]; 

- то есть, порядок объектов в подмассивов совершенно не важно: Я заинтересован только в том, что каждый subarray содержит два объекта - {"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

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

1. Тщательно настройте данные модели (это будет сделано только один раз), чтобы иметь что-то подходящее для применения плоского продукта.
2. Относитесь к «специальному случаю» из более чем одного параметра, запрашивающего одну и ту же строку.

Вся важная логика находится в пределах cartessianProdModified. Важные биты в коде комментируются. Надеюсь, он поможет вам в решении вашей проблемы или, по крайней мере, даст вам некоторые идеи.

Вот fiddle и вот код:

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

Answer 2

Вы можете сделать это вручную с петлями, но вы также можете использовать встроенные функции 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)

Answer 3

Сортировать по алфавиту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 будет отсортирован, вам нужно будет проверить только самый следующий элемент и так далее.

---

Время complextiy:

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

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

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

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

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

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

Но в предположении нормального avergae ситуации, вся процедура имеет время complextiy из:

O (NlogN)

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

Answer 4

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

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

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"]) 

Answer 5

Если вы можете использовать функции ES6, вы можете использовать генераторы, чтобы избежать необходимости создания больших промежуточных массивов. Казалось бы, вы хотите иметь набор множеств со строками, содержащими только уникальные значения. Как также отметили другие, вы можете подойти к этому, начиная с cartesian product объектов ваших 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.