Алгоритм всевозможных комбинаций массивов (венгерский, брутфорс)

Question

Есть задача, которую нужно решить (отслеживание человека по компьютерному зрению), и мне нужно каким-то образом получить все возможные комбинации из 2 массивов.Входные данные: два массива

arr1 = ['a', 'b', 'c'];
arr2 = [1, 2, 3];

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

[
  {a:1, b:2, c:3},
  {a:1, b:3, c:2},
  {a:2, b:1, c:3},
  {a:2, b:3, c:1},
  {a:3, b:1, c:2},
  {a:3, b:2, c:1},
]

Входные массивы могут быть разной длины.Например,

arr1 = [a,b];
arr2 = [1,2,3];
// => 
[
  {a:1, b:2},
  {a:1, b:3},
  {a:2, b:1},
  {a:2, b:3},
  {a:3, b:1},
  {a:3, b:2}
]

Или вот так

arr1 = [a,b,c];
arr2 = [1,2];
// => 
[
  {a:1, b:2},
  {a:1, c:2},
  {b:1, a:2},
  {b:1, c:2},
  {c:1, a:2},
  {c:1, b:2}
]

Идеально будет такая структура

[
  {
    combo: {a:1, b:2, c:3}
  },
  ...
]

... но это на самом деле не имеет значения

Здесь много тем о стеке, подобном этому, но все эти алгоритмы немного отличаются и проще.Все они дают что-то вроде этого:

[a1, a2, b1, b2, c1, c2]

Я получил это до сих пор:

const combos = (arr1, arr2, func) => {
    let result = [];
    for(let item1 of arr1){
        let subcombo = {};
        let subArr1 = Object.assign({}, arr1);
        delete subArr1[item1];
        for(let item2 of arr2){
            subcombo[item] = {};
        }
    }
};
function give1() {
    return 1;
}
let arr1 = ['a', 'b', 'c'];
let arr2 = ['x', 'y', 'z'];
const res = combos(arr1, arr2, give1);
console.log(res);

Answer 1

Вы можете сначала создать функцию для выполнения перестановок с ограничением, а затем на основе длины ключей и значений выполнить перестановку ключей, если keys.length > values.length в противном случае выполнить перестановку значений и после этого создать массив объектов из этого результата.

function permute(data, len) {
  let result = []
  
  function generate(data, n, c) {
    if(!data.length) {
      result.push(c.slice(0, len));
      return;
    }
    
    for(var i = 0; i < data.length; i++) {
      c[n] = data[i]
      let copy = [...data]
      copy.splice(i, 1);
      generate(copy, n + 1, c)
    }
  }
  
  generate(data, 0, [])
  return result;
}

function f(keys, vals) {
  let byKeys = keys.length > vals.length,
  permuted = null
  
  if(byKeys) permuted = permute(keys, vals.length);  
  else permuted = permute(vals, keys.length);
  
  return permuted.map(arr => arr.reduce((r, e, i) => {
    byKeys ? r[e] = vals[i] :  r[keys[i]] = e
    return r;
  }, {}))
}

console.log(f(['a', 'b', 'c'], [1, 2, 3]))
console.log(f(['a', 'b', 'c'], [1, 2]))
console.log(f(['a', 'b'], [1, 2, 3]))