javascript - 所有可能的数组组合算法(匈牙利语，蛮力)

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}
  },
  ...
]

...但这并不重要

像这样的 stackoverflow 上有很多主题，但所有这些算法都有点不同且更容易。他们都给出了这样的东西:

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