深度第一组合算法 [英] Depth-first combination algorithm

问题描述

让我们说我有数组的数组如下：

Let's say I have the following array of arrays:

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

我想找到每个阵列与另一阵列中的元素的元素的所有可能的组合（即adgij'是一种可能性，但不是ABCDE）。

I want to find all possible combinations of the elements of each array with the elements of the other arrays (i.e. 'adgij' is one possibility but not 'abcde').

我可以蛮力它，只是环一切都像这样（的JavaScript）：

I can brute force it and just loop everything like this (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次迭代我会不完整的组合。

The problem with this method is that it is breadth-first, so if I want to stop after n iterations I would have incomplete combinations.

有没有办法使用深度优先方法来获取所有可能的组合？

Is there a way to get all possible combinations using depth-first method?

推荐答案

在伪code一个简单的递归函数。

A simple recursive function in pseudo-code.

我希望这是pretty的不言自明的。

I hope it's pretty self-explanatory.

每个递归步骤挑选，从目前股指的数组中的元素之一，并调用函数的下一个索引。

Each recursive step picks one of the elements from the current index's array, and calls the function for the next index.

电流可以只是一个列表。

someFunction(A, {}, 0)

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

这篇关于深度第一组合算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！