在Java中查找笛卡尔积

Question

我想找到一组元素的笛卡尔积。下面是一个示例

示例 1：

sets : (ab) (bc) (ca)

笛卡尔积是：

abc aba acc aca bbc bba bcc bca

示例 2：

sets : (zyx) b c

笛卡尔积是：

zbc ybc xbc

所以我正在考虑一种在 Java 中执行的算法，它可以找到在编译时定义的特定数量的组的笛卡尔积。

Answer 1

您可以使用 Sets.cartesianProduct() 来自 Google 的方法用于生成笛卡尔积的 Guava 库：

com.google.common.collect.Sets.cartesianProduct(Set[] yourSets)

如果一切都这么简单就好了！

Answer 2

定义您自己的迭代器/迭代器：

import java.util.*;

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

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

并使用您的数据进行测试：

class CartesianIteratorTest {

    public static void main (String[] args) {
        List <Character> la = Arrays.asList (new Character [] {'a', 'b'});
        List <Character> lb = Arrays.asList (new Character [] {'b', 'c'});      
        List <Character> lc = Arrays.asList (new Character [] {'c', 'a'});
        List <List <Character>> llc = new ArrayList <List <Character>> ();
        llc.add (la);
        llc.add (lb);
        llc.add (lc);

        CartesianIterable <Character> ci = new CartesianIterable <Character> (llc);
        for (List<Character> lo: ci)
            show (lo);

        la = Arrays.asList (new Character [] {'x', 'y', 'z'});
        lb = Arrays.asList (new Character [] {'b'});    
        lc = Arrays.asList (new Character [] {'c'});
        llc = new ArrayList <List <Character>> ();
        llc.add (la);
        llc.add (lb);
        llc.add (lc);

        ci = new CartesianIterable <Character> (llc);
        for (List<Character> lo: ci)
            show (lo);    
    }

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

结果：

(abc)
(bbc)
(acc)
(bcc)
(aba)
(bba)
(aca)
(bca)
(xbc)
(ybc)
(zbc)

Answer 3

注意：Set 是不包含重复元素的集合。如果不同集合中有重复元素，则笛卡尔积中的每个集合将仅包含其中一个。

您可以创建一个通用方法来获取笛卡尔积并指定存储它的集合类型。例如，Set 或 List。

使用map 和reduce 方法的笛卡尔积

• map 方法将集合中的每个元素表示为单例集合，并指定结果的格式。

• reduce 方法将成对的 2D 集合求和为单个 2D 集合。

<一href="https://tio.run/##rVZNb9swDL33V3A5FHbgOmuOWZqtDQrssAJDcxx2UG2mUSpLhiS3y9b@9oySP9M4aQfMgJFQIh8p8pHymj2ys3X6sN3yLFfawpoW4sJyEQ8/neytLQuZW K5kvCjyXHDUPTrGamSZMz/JizvBE0gEMwZuGJfw5wToqdaNZZZ@HhVPIaPdYGE1l/c/fgLT9yaslN3zjRs7XSC9XmM2A4PWwIXfiNUyaDTrh5Td@uByEMHgahBGzcqVW5l3V@Zu5XIQhhT yYY9JTiK5TJi2aDiT37VKi8QGX5lZ0dZkIvEp8oER0A5OCdYCObkP6VJrtnGbu1gN2GgEq rB5YSNQOkVNWdvAI9ObRmOxMRazmlLTinNxZIQORSs@BP0DYie24souj1n4pYxgNh6XxEL7k TLMMEiUM2BUClxSWEwV6hoBadiTzykzOlfBmpuKRU3dyebyO5SvD6fUMvKLd5FgbocAMPa3Fw8a3PcYabaFlb6zVlq8emXrsumSQlzWrYbJCWJ4L7AEa9XB@eh3BLeAvizI1MG9s6Hyzxu EeP3ZYXreg03T5jLownw9hu4J1O4solawweQC@7NTR5wstakOtiCCVBVkI0ViRcuBreHHhN@D5uaRCJYd1Wp3QEq7NtanGRBDudS5FJJU887BMpl7ALLeb/dR2nnjJBcUbkA6c@WPChyq 201Mnxob/xiCEGXzs9akx12gcjZAlqy6nWJfWjDIChjpEoFVyj2vdiDKWd8I5fOAdA3Tqi3 KE0mzCMK5cBFUhlTaxVW1VfR3C8DAsna3Em1a8mh2OoNeXMwv6PBCyKbKM1f2eM06EoT9cS mrpo@XSSIzGwCXoPHKq47BK1PnbmXKkVdkdl971O122TBHM3lCqvcl55XX8ttcd7zJh1F/0 kmerGk4cI0RvvX0Q492il4FF5ZnGbwe0d7KWHZNJeax/AHkn345WR7gLzt8AbZX@I@sUTSr 9xA3SgIByNjiP@yxT@loY7OTDxF69At@93EblbeT7nu5UoAG4UmlUTS3X90ulie0WUxrj7p b0ds1Eb0ZuddNXv9Dcqb7/3j2Z@4Zld6aUoPFa0YfTYOB7qCdbfcl1Ji4e99nTJuFlu/0L" rel="nofollow noreferrer" title="Java (JDK) – 在线尝试">在线尝试！

public static void main(String[] args) {
    List<Set<String>> sets = List.of(
            Set.of("A", "B"), Set.of("B", "C"), Set.of("C", "A"));

    List<Set<String>> cpSet = cartesianProduct(HashSet::new, sets);
    List<List<String>> cpList = cartesianProduct(ArrayList::new, sets);

    // output, order may vary
    System.out.println(toString(cpSet));
    //ABC, AB, AC, AC, BC, BA, BC, BCA
    System.out.println(toString(cpList));
    //ABC, ABA, ACC, ACA, BBC, BBA, BCC, BCA
}

/**
 * @param cols the input collection of collections
 * @param nCol the supplier of the output collection
 * @param <E>  the type of the element of the collection
 * @param <R>  the type of the return collections
 * @return List<R> the cartesian product of the multiple collections
 */
public static <E, R extends Collection<E>> List<R> cartesianProduct(
        Supplier<R> nCol, Collection<? extends Collection<E>> cols) {
    // check if the input parameters are not null
    if (nCol == null || cols == null) return null;
    return cols.stream()
        // non-null and non-empty collections
        .filter(col -> col != null && col.size() > 0)
        // represent each element of a collection as a singleton collection
        .map(col -> col.stream()
            .map(e -> Stream.of(e).collect(Collectors.toCollection(nCol)))
            // Stream<List<R>>
            .collect(Collectors.toList()))
        // summation of pairs of inner collections
        .reduce((col1, col2) -> col1.stream()
            // combinations of inner collections
            .flatMap(inner1 -> col2.stream()
                // concatenate into a single collection
                .map(inner2 -> Stream.of(inner1, inner2)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toCollection(nCol))))
            // list of combinations
            .collect(Collectors.toList()))
        // otherwise an empty list
        .orElse(Collections.emptyList());
}

// supplementary method, returns a formatted string
static <E extends String> String toString(List<? extends Collection<E>> cols) {
    return cols.stream().map(col -> String.join("", col))
            .collect(Collectors.joining(", "));
}

---

^{另请参阅：任意数量集合的笛卡尔积}