生成多个列表中的所有组合

Question

生成多个列表中的所有组合给定未知数量的列表，每个列表具有未知长度，我需要生成具有所有可能的唯一组合的单个列表。例如，给出以下列表：X: [A, B, C] Y: [W, X, Y, Z]然后我应该能够生成12种组合：[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]如果添加了3个元素的第三个列表，我将有36个组合，依此类推。关于如何用Java做到这一点的任何想法？（伪代码也可以）

Answer 1

你需要递归：

假设您的所有列表都在lists，这是一个列表列表。让我们result列出您所需的排列。你可以像这样实现它：

void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
    if (depth == lists.size()) {
        result.add(current);
        return;
    }

    for (int i = 0; i < lists.get(depth).size(); i++) {
        generatePermutations(lists, result, depth + 1, current + lists.get(depth).get(i));
    }}

最终的电话会是这样的：

generatePermutations(lists, result, 0, "");

Answer 2

这个话题派上了用场。我用Java完全重写了以前的解决方案，更加用户友好。此外，我使用集合和泛型来获得更大的灵活性：

/**
 * Combines several collections of elements and create permutations of all of them, taking one element from each
 * collection, and keeping the same order in resultant lists as the one in original list of collections.
 * 
 * <ul>Example
 * <li>Input  = { {a,b,c} , {1,2,3,4} }</li>
 * <li>Output = { {a,1} , {a,2} , {a,3} , {a,4} , {b,1} , {b,2} , {b,3} , {b,4} , {c,1} , {c,2} , {c,3} , {c,4} }</li>
 * </ul>
 * 
 * @param collections Original list of collections which elements have to be combined.
 * @return Resultant collection of lists with all permutations of original list.
 */public static <T> Collection<List<T>> permutations(List<Collection<T>> collections) {
  if (collections == null || collections.isEmpty()) {
    return Collections.emptyList();
  } else {
    Collection<List<T>> res = Lists.newLinkedList();
    permutationsImpl(collections, res, 0, new LinkedList<T>());
    return res;
  }}/** Recursive implementation for {@link #permutations(List, Collection)} */private static <T> void permutationsImpl(List<Collection<T>> ori, Collection<List<T>> res, int d, List<T> current) {
  // if depth equals number of original collections, final reached, add and return
  if (d == ori.size()) {
    res.add(current);
    return;
  }

  // iterate from current collection and copy 'current' element N times, one for each element
  Collection<T> currentCollection = ori.get(d);
  for (T element : currentCollection) {
    List<T> copy = Lists.newLinkedList(current);
    copy.add(element);
    permutationsImpl(ori, res, d + 1, copy);
  }}

我正在使用guava库来创建集合。

Answer 3

此操作称为笛卡尔积。Guava提供了一个实用功能：Lists.cartesianProduct