任意数量集合的笛卡尔积

Question

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

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

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

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

Answer 1

基于索引的解决方案

使用索引是一种快速、内存高效且可以处理任意数量的集合的替代方案。 实现 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]]);
        }
    }
}

Answer 2

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

两个提示：

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

Answer 3

这是一个 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 (")");
    }
}

它是如何完成的？ 我们需要一个 Iterable，以使用简化的 for 循环，并且必须从 Iterable 返回一个 Iterator。
我们返回一个对象列表 - 这可能是一个 Set 而不是 List，但是 Set 没有索引访问，因此使用 Set 而不是 List 来实现它会更复杂一些。 如果不是通用解决方案，对象可以满足多种用途，但泛型允许更多限制。

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;
            }
        }
    }
}

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

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);
    }
}

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

结果：

(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, )

Answer 4

这是一个迭代器，它给出二维数组的笛卡尔积，其中数组组件代表问题中的集合（人们总是可以将实际的集合转换为数组):

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;
    }
}

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

使用示例：

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));
}

输出：

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

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

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

Answer 5

您可以获取任意数量的不同类型集合的笛卡尔积并将其存储到对象Set<的集合集合中;使用 Java 9 Streams 设置

在线试用！

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    // incorrect incoming data
    if (sets == null) return Collections.emptySet();
    return Arrays.stream(sets)
            // non-null and non-empty sets
            .filter(set -> set != null && set.size() > 0)
            // represent each set element as Set<Object>
            .map(set -> set.stream().map(Set::<Object>of)
                    // Stream<Set<Set<Object>>>
                    .collect(Collectors.toSet()))
            // summation of pairs of inner sets
            .reduce((set1, set2) -> set1.stream()
                    // combinations of inner sets
                    .flatMap(inner1 -> set2.stream()
                            // merge two inner sets into one
                            .map(inner2 -> Stream.of(inner1, inner2)
                                    .flatMap(Set::stream)
                                    .collect(Collectors.toCollection(
                                            LinkedHashSet::new))))
                    // set of combinations
                    .collect(Collectors.toCollection(LinkedHashSet::new)))
            // returns Set<Set<Object>>, otherwise an empty set
            .orElse(Collections.emptySet());
}

public static void main(String[] args) {
    Set<Integer> set1 = Set.of(1, 2, 3);
    Set<String> set2 = Set.of("A", "B", "C");
    Set<Object> set3 = Set.of(new Time(0));

    Set<Set<Object>> sets = cartesianProduct(set1, set2, set3);
    // output
    sets.forEach(System.out::println);
}

输出：

[1, A, 03:00:00]
[1, B, 03:00:00]
[1, C, 03:00:00]
[2, A, 03:00:00]
[2, B, 03:00:00]
[2, C, 03:00:00]
[3, A, 03:00:00]
[3, B, 03:00:00]
[3, C, 03:00:00]

---

^{另请参阅：如何创建数据类似于三个不同类型列表的笛卡尔积的结构？}

Answer 6

是的，有函数式 Java。

对于集合 s：

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

Answer 7

例如，对于整数集，一个简单的解决方案应如下所示：

void printCombination(List<Set<Integer>> listSet, Set<Integer> combination) {
    if (listSet.isEmpty()) {
        System.out.println("a combination :" + combination);

        return;
    }

    Set<Integer> intSet = listSet.get(0);
    for (Integer it : intSet) {
        Set<Integer> combination1 = new HashSet<Integer>();
        combination1.addAll(combination);
        combination1.add(it);

        List<Set<Integer>> listSet1 = new ArrayList<Set<Integer>>();
        listSet1.addAll(listSet);
        listSet1.remove(0);
        this.printCombination(listSet1, combination1);
    }

} 

Answer 8

您可以通过此库应用一个名为Seq的简单生成器接口。 与 不同Guava 的 cartesianProduct，集合/列表/迭代不需要位于相同的泛型类型绑定 B 内，所有类型都受欢迎。 您所需要做的就是将乘积编写为普通的嵌套 for 循环。

public static void main(String[] args) {
    List<String> ls1 = Arrays.asList("a", "b");
    List<Integer> ls2 = Arrays.asList(1, 2);
    List<Character> ls3 = Arrays.asList('x', 'y');

    Seq<String> seq = c -> {
        for (String s : ls1) {
            for (Integer i : ls2) {
                for (Character d : ls3) {
                    c.accept(s + i + d);
                }
            }
        }
    };

    System.out.println(seq.toSet());
}

结果将是

[a2x, a1y, b1x, b2y, a1x, a2y, b2x, b1y]

Answer 9

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

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

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;
}

请注意，不可能在返回的集合中保留任何通用类型信息。 如果您事先知道要获取多少个集合的乘积，则可以定义一个通用元组来保存那么多元素（例如 Triple），但是有Java 中无法拥有任意数量的泛型参数。

Answer 10

这是一个非常老的问题，但为什么不使用 Guava 的笛卡尔积？

Answer 11

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

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;
}

示例：

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

将产生以下结果：

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