algorithm - 深度优先组合算法

Question

假设我有以下数组:

A = [
  ['a', 'b', 'c'],
  ['d', 'e', 'f'],
  ['g', 'h'],
  ['i'],
  ['j', 'k', 'l']
]

我想找到每个数组的元素与其他数组的元素的所有可能组合(即“adgij”是一种可能性，但不是“abcde”)。

我可以暴力破解它并像这样循环所有内容 (javascript):

var A = [
      ['a', 'b', 'c'],
      ['d', 'e', 'f'],
      ['g', 'h'],
      ['i'],
      ['j', 'k', 'l']
    ],
    combinations,
    newCombinations = [];

A.forEach(function(a, index) {
  newCombinations = [];

  if (index === 0) {
    newCombinations = a;
  } else {
    a.forEach(function(val){
      combinations.forEach(function(combination){
        newCombinations.push(combination + val);
      });
    });
  }

  combinations = newCombinations;
});

此方法的问题在于它是广度优先的，因此如果我想在 n 次迭代后停止，我将得到不完整的组合。

有没有办法使用深度优先方法得到所有可能的组合？

Answer 1

一个简单的伪代码递归函数。

每个递归步骤从当前索引的数组中选取一个元素，并为下一个索引调用该函数。

current 可以只是一个列表。

printAllCombinations(A, {}, 0)

printAllCombinations(A, current, index)
  if index == A.length
    print current
    return
  for each element e in A[index]
    current.addToBack(e)
    printAllCombinations(A, current, index + 1)
    current.removeLast(e)