迭代计算任意数量集合的笛卡尔积

algorithm list java set cartesian-product

2022-09-02 01:21:02

我想计算Java中任意数量的非空集合的笛卡尔积。

我已经写了迭代代码...

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {
    List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
    List<T> elements = new ArrayList<T>(list.size());
    List<Set<T>> toRet = new ArrayList<Set<T>>();
    for (int i = 0; i < list.size(); i++) {
        iterators.add(list.get(i).iterator());
        elements.add(iterators.get(i).next());
    }
    for (int j = 1; j >= 0;) {
        toRet.add(Sets.newHashSet(elements));
        for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {
            iterators.set(j, list.get(j).iterator());
            elements.set(j, iterators.get(j).next());
        }
        elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());
    }
    return toRet;
}

...但我发现它相当不优雅。有人有一个更好的，仍然是迭代的解决方案？使用一些奇妙的功能性方法的解决方案？否则。。。关于如何改进它的建议？错误？

答案 1

我编写了一个解决方案，它不需要您在内存中填充大量集合。不幸的是，所需的代码长达数百行。您可能需要等到它出现在番石榴项目（https://github.com/google/guava）中，我希望到今年年底。不好意思。:(

请注意，如果笛卡尔积法的集合数是编译时已知的固定数，则可能不需要这样的实用程序 - 您可以只使用该数量的嵌套 for 循环。

编辑：代码现已发布。

Sets.cartesianProduct()

我想你会对它非常满意。它只创建您要求的单个列表;不会用它们的所有MxNxPxQ填充内存。

如果你想检查源，它就在这里。

享受！

答案 2

使用Google Guava 19和Java 8非常简单：

假设您有要关联的所有数组的列表...

public static void main(String[] args) {
  List<String[]> elements = Arrays.asList(
    new String[]{"John", "Mary"}, 
    new String[]{"Eats", "Works", "Plays"},
    new String[]{"Food", "Computer", "Guitar"}
  );

  // Create a list of immutableLists of strings
  List<ImmutableList<String>> immutableElements = makeListofImmutable(elements);

  // Use Guava's Lists.cartesianProduct, since Guava 19
  List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements);

  System.out.println(cartesianProduct);
}

制作不可变列表列表的方法如下：

/**
 * @param values the list of all profiles provided by the client in matrix.json
 * @return the list of ImmutableList to compute the Cartesian product of values
 */
private static List<ImmutableList<String>> makeListofImmutable(List<String[]> values) {
  List<ImmutableList<String>> converted = new LinkedList<>();
  values.forEach(array -> {
    converted.add(ImmutableList.copyOf(array));
  });
  return converted;
}

输出如下：

[
  [John, Eats, Food], [John, Eats, Computer], [John, Eats, Guitar],
  [John, Works, Food], [John, Works, Computer], [John, Works, Guitar], 
  [John, Plays, Food], [John, Plays, Computer], [John, Plays, Guitar],
  [Mary, Eats, Food], [Mary, Eats, Computer], [Mary, Eats, Guitar],
  [Mary, Works, Food], [Mary, Works, Computer], [Mary, Works, Guitar],
  [Mary, Plays, Food], [Mary, Plays, Computer], [Mary, Plays, Guitar]
]