Java中任意集的笛卡尔积

Cartesian product of arbitrary sets in Java

提问by mgamer

Do you know some neat Java libaries that allow you to make cartesian product of two (or more) sets?

您是否知道一些简洁的 Java 库可以让您制作两个（或更多）集合的笛卡尔积？

For example: I have three sets. One with objects of class Person, second with objects of class Gift and third with objects of class GiftExtension.

例如：我有三套。第一个是Person 类的对象，第二个是Gift 类的对象，第三个是GiftExtension 类的对象。

I want to generate one set containing all possible triples Person-Gift-GiftExtension.

我想生成一组包含所有可能的三元组 Person-Gift-GiftExtension。

The number of sets might vary so I cannot do this in nested foreach loop. Under some conditions my application needs to make a product of Person-Gift pair, sometimes it is triple Person-Gift-GiftExtension, sometimes there might even be sets Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension, etc.

集合的数量可能会有所不同，因此我无法在嵌套的 foreach 循环中执行此操作。在某些情况下，我的应用程序需要制作Person-Gift pair的产品，有时是三重Person-Gift-GiftExtension，有时甚至可能有Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension等。

采纳答案by Michael Myers

Edit:Previous solutions for two sets removed. See edit history for details.

编辑：删除了两组以前的解决方案。有关详细信息，请参阅编辑历史记录。

Here is a way to do it recursively for an arbitrary number of sets:

这是一种对任意数量的集合递归执行的方法：

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Note that it is impossible to keep any generic type information with the returned sets. If you knew in advance how many sets you wanted to take the product of, you could define a generic tuple to hold that many elements (for instance Triple<A, B, C>), but there is no way to have an arbitrary number of generic parameters in Java.

请注意，不可能在返回的集合中保留任何泛型类型信息。如果您事先知道要取多少个集合，您可以定义一个泛型元组来保存这么多元素（例如Triple<A, B, C>），但在 Java 中无法拥有任意数量的泛型参数。

回答by Michael Borgwardt

The number of sets might vary so I cannot do this in nested foreach loop.

集合的数量可能会有所不同，因此我无法在嵌套的 foreach 循环中执行此操作。

Two hints:

两个提示：

• A x B x C = A x (B x C)
• Recursion

• A x B x C = A x (B x C)
• 递归

回答by Michael Borgwardt

Yes, there is Functional Java.

是的，有Functional Java。

For a set (s):

对于一组（s）：

s.bind(P.p2(), s);

s.bind(P.p2(), s);

回答by Philipp Meister

The method below creates the cartesian product of a list of list of strings:

下面的方法创建字符串列表的笛卡尔积：

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                resultList.add(condition);
                resultList.addAll(remainingList);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}

Example:

例子：

System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));

would yield this:

会产生这个：

[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]

回答by user unknown

Here is an Iterable, which allows you to use a simplified for-loop:

这是一个 Iterable，它允许您使用简化的 for 循环：

import java.util.*;

// let's begin with the demo. Instead of Person and Gift, 
// I use the well known char and int. 
class CartesianIteratorTest {

    public static void main (String[] args) {
        List <Object> lc = Arrays.asList (new Object [] {'A', 'B', 'C', 'D'});
        List <Object> lC = Arrays.asList (new Object [] {'a', 'b', 'c'});   
        List <Object> li = Arrays.asList (new Object [] {1, 2, 3, 4});
            // sometimes, a generic solution like List <List <String>>
            // might be possible to use - typically, a mixture of types is 
            // the common nominator 
        List <List <Object>> llo = new ArrayList <List <Object>> ();
        llo.add (lc);
        llo.add (lC);
        llo.add (li);

        // Preparing the List of Lists is some work, but then ...    
        CartesianIterable <Object> ci = new CartesianIterable <Object> (llo);

        for (List <Object> lo: ci)
            show (lo);
    }

    public static void show (List <Object> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o + ", ");
        System.out.println (")");
    }
}

How is it done? We need an Iterable, to use the simplified for-loop, and an Iterator has to be returned from the Iterable. We return a List of Objects - this could be a Set instead of List, but Set has no indexed access, so it would be a bit more complicated, to implement it with Set instead of List. Instead of a generic solution, Object would have been fine for many purposes, but generics allow for more restrictions.

它是如何完成的？我们需要一个 Iterable 来使用简化的 for 循环，并且必须从 Iterable 返回一个 Iterator。我们返回一个对象列表——这可能是一个集合而不是列表，但是集合没有索引访问，所以它会更复杂一点，用集合而不是列表来实现它。与通用解决方案不同，Object 可以用于许多目的，但泛型允许更多限制。

class CartesianIterator <T> implements Iterator <List <T>> {

    private final List <List <T>> lilio;    
    private int current = 0;
    private final long last;

    public CartesianIterator (final List <List <T>> llo) {
        lilio = llo;
        long product = 1L;
        for (List <T> lio: lilio)
            product *= lio.size ();
        last = product;
    } 

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List<T> get (final int n, final List <List <T>> lili) {
        switch (lili.size ())
        {
            case 0: return new ArrayList <T> (); // no break past return;
            default: {
                List <T> inner = lili.get (0);
                List <T> lo = new ArrayList <T> ();
                lo.add (inner.get (n % inner.size ()));
                lo.addAll (get (n / inner.size (), lili.subList (1, lili.size ())));
                return lo;
            }
        }
    }
}

The mathematical work is done in the 'get'-method. Think about 2 sets of 10 elements. You have a total of 100 combinations, enumerated from 00, 01, 02, ... 10, ... to 99. For 5 X 10 elements 50, for 2 X 3 elements 6 combinations. The modulo of the sublist size helps to pick one element for each iteration.

数学工作是在“get”方法中完成的。考虑 2 组 10 个元素。您总共有 100 种组合，从 00、01、02、... 10、... 到 99 枚举。对于 5 X 10 元素为 50，对于 2 X 3 元素为 6 种组合。子列表大小的模有助于为每次迭代选择一个元素。

Iterable i the least interesting thing here:

Iterable 我在这里最不有趣的事情：

class CartesianIterable <T> implements Iterable <List <T>> {

    private List <List <T>> lilio;  

    public CartesianIterable (List <List <T>> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new CartesianIterator <T> (lilio);
    }
}

To implement Iterable, which allows the for-each kind of loop, we have to implement iterator (), and for Iterator we have to implement hasNext (), next () and remove ().

为了实现允许for-each循环的Iterable，我们必须实现iterator()，而对于Iterator，我们必须实现hasNext()、next()和remove()。

Result:

结果：

(A, a, 1, )
(B, a, 1, )
(C, a, 1, )
(D, a, 1, )
(A, b, 1, )
(B, b, 1, )
(C, b, 1, )
(D, b, 1, )
...
(A, a, 2, )
...
(C, c, 4, )
(D, c, 4, )

回答by Remko Popma

Index-based solution

基于索引的解决方案

Working with the indices is an alternative that is fast and memory-efficient and can handle any number of sets. Implementing Iterable allows easy use in a for-each loop. See the #main method for a usage example.

使用索引是一种快速且节省内存的替代方法，并且可以处理任意数量的集合。实现 Iterable 允许在 for-each 循环中轻松使用。有关用法示例，请参阅 #main 方法。

public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> {

    private final int[] _lengths;
    private final int[] _indices;
    private boolean _hasNext = true;

    public CartesianProduct(int[] lengths) {
        _lengths = lengths;
        _indices = new int[lengths.length];
    }

    public boolean hasNext() {
        return _hasNext;
    }

    public int[] next() {
        int[] result = Arrays.copyOf(_indices, _indices.length);
        for (int i = _indices.length - 1; i >= 0; i--) {
            if (_indices[i] == _lengths[i] - 1) {
                _indices[i] = 0;
                if (i == 0) {
                    _hasNext = false;
                }
            } else {
                _indices[i]++;
                break;
            }
        }
        return result;
    }

    public Iterator<int[]> iterator() {
        return this;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Usage example. Prints out
     * 
     * <pre>
     * [0, 0, 0] a, NANOSECONDS, 1
     * [0, 0, 1] a, NANOSECONDS, 2
     * [0, 0, 2] a, NANOSECONDS, 3
     * [0, 0, 3] a, NANOSECONDS, 4
     * [0, 1, 0] a, MICROSECONDS, 1
     * [0, 1, 1] a, MICROSECONDS, 2
     * [0, 1, 2] a, MICROSECONDS, 3
     * [0, 1, 3] a, MICROSECONDS, 4
     * [0, 2, 0] a, MILLISECONDS, 1
     * [0, 2, 1] a, MILLISECONDS, 2
     * [0, 2, 2] a, MILLISECONDS, 3
     * [0, 2, 3] a, MILLISECONDS, 4
     * [0, 3, 0] a, SECONDS, 1
     * [0, 3, 1] a, SECONDS, 2
     * [0, 3, 2] a, SECONDS, 3
     * [0, 3, 3] a, SECONDS, 4
     * [0, 4, 0] a, MINUTES, 1
     * [0, 4, 1] a, MINUTES, 2
     * ...
     * </pre>
     */
    public static void main(String[] args) {
        String[] list1 = { "a", "b", "c", };
        TimeUnit[] list2 = TimeUnit.values();
        int[] list3 = new int[] { 1, 2, 3, 4 };

        int[] lengths = new int[] { list1.length, list2.length, list3.length };
        for (int[] indices : new CartesianProduct(lengths)) {
            System.out.println(Arrays.toString(indices) //
                    + " " + list1[indices[0]] //
                    + ", " + list2[indices[1]] //
                    + ", " + list3[indices[2]]);
        }
    }
}

回答by Martin Andersson

This is a pretty old question, but why not use Guava's cartesianProduct?

这是一个很老的问题，但为什么不使用Guava 的 cartesianProduct呢？

回答by Halle Knast

Here is an Iteratorthat gives the cartesian product of a two-dimensional array, where the arrays components represent the sets from the question (one can always convert actual Sets to arrays):

这是一个Iterator给出二维数组的笛卡尔积，其中数组组件表示问题中的集合（总是可以将实际Sets转换为数组）：

public class CartesianIterator<T> implements Iterator<T[]> {
    private final T[][] sets;
    private final IntFunction<T[]> arrayConstructor;

    private int count = 0;
    private T[] next = null;

    public CartesianIterator(T[][] sets, IntFunction<T[]> arrayConstructor) {
        Objects.requireNonNull(sets);
        Objects.requireNonNull(arrayConstructor);

        this.sets = copySets(sets);
        this.arrayConstructor = arrayConstructor;
    }

    private static <T> T[][] copySets(T[][] sets) {
        // If any of the arrays are empty, then the entire iterator is empty.
        // This prevents division by zero in `hasNext`.
        for (T[] set : sets) {
            if (set.length == 0) {
                return Arrays.copyOf(sets, 0);
            }
        }
        return sets.clone();
    }

    @Override
    public boolean hasNext() {
        if (next != null) {
            return true;
        }

        int tmp = count;
        T[] value = arrayConstructor.apply(sets.length);
        for (int i = 0; i < value.length; i++) {
            T[] set = sets[i];

            int radix = set.length;
            int index = tmp % radix;

            value[i] = set[index];

            tmp /= radix;
        }

        if (tmp != 0) {
            // Overflow.
            return false;
        }

        next = value;
        count++;

        return true;
    }

    @Override
    public T[] next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        T[] tmp = next;
        next = null;
        return tmp;
    }
}

The basic idea is to treat countas a multi-radix number (digit ihas its own radix which equals the length of the i'th "set"). Whenever we have to resolve next(that is, when hasNext()is called and nextis null), we decompose the number into its digits in this multi-radix. These digits are now used as the indices from which we draw elements from the different sets.

基本思想是将其count视为多基数（数字i有自己的基数，等于i“第”组的长度）。每当我们必须解析时next（即，何时hasNext()被调用和next是null），我们将数字分解为这个多基数中的数字。这些数字现在用作我们从不同集合中绘制元素的索引。

Example use:

使用示例：

String[] a = { "a", "b", "c"};
String[] b = { "X" };
String[] c = { "r", "s" };

String[][] abc = { a, b, c };

Iterable<String[]> it = () -> new CartesianIterator<>(abc, String[]::new);
for (String[] s : it) {
    System.out.println(Arrays.toString(s));
}

Output:

输出：

[a, X, r]
[b, X, r]
[c, X, r]
[a, X, s]
[b, X, s]
[c, X, s]

If one doesn't like arrays, the code is trivially convertible into using collections.

如果不喜欢数组，代码可以轻松转换为使用集合。

I guess this is more or less similar to the answer given by "user unknown", only without recursion and collections.

我想这或多或少类似于“用户未知”给出的答案，只是没有递归和集合。

回答by Masoud

how about using odl.com.google.common18.collect.Sets and calling Sets.cartesianProduct() method

如何使用 odl.com.google.common18.collect.Sets 并调用 Sets.cartesianProduct() 方法