`
kanpiaoxue
  • 浏览: 1777520 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

笛卡尔积：Cartesian product 示例:java

 
阅读更多

 

 

笛卡尔积： https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E4%B9%98%E7%A7%AF/6323173?fr=aladdin

 

import org.apache.commons.collections4.CollectionUtils;

import com.google.common.base.Joiner;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * CartesianProductUtils.java
 *
 * @author kanpiaoxue
 * @version 1.0
 *          Create Time 2018年11月27日 下午10:28:50
 *          Description : 笛卡尔积：Cartesian product 工具类
 */
public class CartesianProductUtils {

    /**
     *
     * @param datas
     *            笛卡尔积维度数据
     * @return 笛卡尔积结果
     * @author kanpiaoxue
     * @CreateTime: 2018/11/28 10:12:21
     * @Description: 根据笛卡尔积维度数据计算笛卡尔积结果
     *
     *               <pre>
     *               List<List<String>> datas = Lists.newArrayList();
     *               List<String> a = Lists.newArrayList("A", "B");
     *               datas.add(a);
     *               List<String> b = Lists.newArrayList("C", "D", "E");
     *               datas.add(b);
     *               List<String> c = Lists.newArrayList("F", "G");
     *               datas.add(c);
     *               List<String> d = Lists.newArrayList("H", "I", "J", "K");
     *               datas.add(d);
     *
     *               List<List<String>> rs = cartesianProduct(datas);
     *               rs.forEach(System.out::println);
     *               ==================== output ====================
     *               [A, C, F, H]
     *               [A, C, F, I]
     *               [A, C, F, J]
     *               [A, C, F, K]
     *               [A, C, G, H]
     *               [A, C, G, I]
     *               [A, C, G, J]
     *               [A, C, G, K]
     *               [A, D, F, H]
     *               [A, D, F, I]
     *               [A, D, F, J]
     *               [A, D, F, K]
     *               [A, D, G, H]
     *               [A, D, G, I]
     *               [A, D, G, J]
     *               [A, D, G, K]
     *               [A, E, F, H]
     *               [A, E, F, I]
     *               [A, E, F, J]
     *               [A, E, F, K]
     *               [A, E, G, H]
     *               [A, E, G, I]
     *               [A, E, G, J]
     *               [A, E, G, K]
     *               [B, C, F, H]
     *               [B, C, F, I]
     *               [B, C, F, J]
     *               [B, C, F, K]
     *               [B, C, G, H]
     *               [B, C, G, I]
     *               [B, C, G, J]
     *               [B, C, G, K]
     *               [B, D, F, H]
     *               [B, D, F, I]
     *               [B, D, F, J]
     *               [B, D, F, K]
     *               [B, D, G, H]
     *               [B, D, G, I]
     *               [B, D, G, J]
     *               [B, D, G, K]
     *               [B, E, F, H]
     *               [B, E, F, I]
     *               [B, E, F, J]
     *               [B, E, F, K]
     *               [B, E, G, H]
     *               [B, E, G, I]
     *               [B, E, G, J]
     *               [B, E, G, K]
     *               </pre>
     */
    public static <T> List<List<T>> cartesianProduct(List<List<T>> datas) {
        if (CollectionUtils.isEmpty(datas)) {
            // 如果为空列表，返回空列表
            return Lists.newArrayList();
        }
        // 使用 LinkedList 的链表特性
        LinkedList<List<T>> dims = Lists.newLinkedList(datas);
        // LinkedList 中取出第一个元素作为起始维度
        List<List<T>> startDim = dims.poll().stream().map(data -> {
            return Lists.newArrayList(data);
        }).collect(Collectors.toList());

        List<List<T>> result = Lists.newArrayList();
        recursion(startDim, dims, result);
        return result;
    }

    /**
     * @param datas
     *            笛卡尔积维度集合
     * @return 维度数量（层级）
     * @author kanpiaoxue
     *         Create Time 2018年11月28日 上午8:34:08
     *         Description : 计算得到笛卡尔积维度集合的维度数量（层级）
     */
    public static <T> int cartesianProductSize(List<List<T>> datas) {
        if (CollectionUtils.isEmpty(datas)) {
            return 0;
        }
        int size = 1;
        for (List<T> data : datas) {
            int tempSize = CollectionUtils.isNotEmpty(data) ? data.size() : 1;
            size *= tempSize;
        }
        return size;
    }

    /**
     * @param separator
     *            分隔符
     * @param datas
     *            笛卡尔积维度集合
     * @return 拼接的字符串
     * @author kanpiaoxue
     *         Create Time 2018年11月28日 上午8:35:47
     *         Description : 将各个维度使用分隔符进行拼接
     */
    public static <T> List<String> join(String separator, List<List<T>> datas) {
        Preconditions.checkNotNull(separator, "separator is null");
        if (CollectionUtils.isEmpty(datas)) {
            return Lists.newArrayList();
        }
        String tmpSeparator = separator.trim();
        return datas.stream().map(e -> {
            return Joiner.on(tmpSeparator).skipNulls().join(e);
        }).collect(Collectors.toList());
    }

    /**
     * @param args
     * @author kanpiaoxue
     *         Create Time 2018年11月27日 下午10:28:51
     */
    public static void main(String[] args) {
        List<List<String>> datas = Lists.newArrayList();
        List<String> a = Lists.newArrayList("A", "B");
        datas.add(a);
        List<String> b = Lists.newArrayList("C", "D", "E");
        datas.add(b);
        List<String> c = Lists.newArrayList("F", "G");
        datas.add(c);
        List<String> d = Lists.newArrayList("H", "I", "J", "K");
        datas.add(d);

        List<List<String>> rs = cartesianProduct(datas);
        System.out.println("result:" + rs);
        rs.forEach(System.out::println);

        int cartesianProductSize = cartesianProductSize(datas);
        System.out.println("cartesianProductSize:" + cartesianProductSize);
        System.out.println("rs.size:" + rs.size());

        join("=", rs).forEach(System.out::println);
    }

    /**
     * @param start
     *            开始维度：笛卡尔积的第一个集合
     * @param leftDatas
     *            剩余维度：笛卡尔积剩下的其他集合
     * @param result
     *            结果
     * @author kanpiaoxue
     *         Create Time 2018年11月28日 上午8:27:05
     *         Description : 递归求取笛卡尔积
     */
    private static <T> void recursion(List<List<T>> start, LinkedList<List<T>> leftDatas,
            List<List<T>> result) {
        if (!leftDatas.isEmpty()) {
            List<T> leftElement = leftDatas.poll();
            List<List<T>> newStart = start.stream().flatMap(startElement -> {
                return leftElement.stream().map(e -> {
                    List<T> tmpList = Lists.newArrayList(startElement);
                    tmpList.add(e);
                    return tmpList;
                });
            }).collect(Collectors.toList());
            recursion(newStart, leftDatas, result);
        } else {
            result.addAll(start);
        }
    }

}

 

 

 

=== output: 写道
result:[[A, C, F, H], [A, C, F, I], [A, C, F, J], [A, C, F, K], [A, C, G, H], [A, C, G, I], [A, C, G, J], [A, C, G, K], [A, D, F, H], [A, D, F, I], [A, D, F, J], [A, D, F, K], [A, D, G, H], [A, D, G, I], [A, D, G, J], [A, D, G, K], [A, E, F, H], [A, E, F, I], [A, E, F, J], [A, E, F, K], [A, E, G, H], [A, E, G, I], [A, E, G, J], [A, E, G, K], [B, C, F, H], [B, C, F, I], [B, C, F, J], [B, C, F, K], [B, C, G, H], [B, C, G, I], [B, C, G, J], [B, C, G, K], [B, D, F, H], [B, D, F, I], [B, D, F, J], [B, D, F, K], [B, D, G, H], [B, D, G, I], [B, D, G, J], [B, D, G, K], [B, E, F, H], [B, E, F, I], [B, E, F, J], [B, E, F, K], [B, E, G, H], [B, E, G, I], [B, E, G, J], [B, E, G, K]]
[A, C, F, H]
[A, C, F, I]
[A, C, F, J]
[A, C, F, K]
[A, C, G, H]
[A, C, G, I]
[A, C, G, J]
[A, C, G, K]
[A, D, F, H]
[A, D, F, I]
[A, D, F, J]
[A, D, F, K]
[A, D, G, H]
[A, D, G, I]
[A, D, G, J]
[A, D, G, K]
[A, E, F, H]
[A, E, F, I]
[A, E, F, J]
[A, E, F, K]
[A, E, G, H]
[A, E, G, I]
[A, E, G, J]
[A, E, G, K]
[B, C, F, H]
[B, C, F, I]
[B, C, F, J]
[B, C, F, K]
[B, C, G, H]
[B, C, G, I]
[B, C, G, J]
[B, C, G, K]
[B, D, F, H]
[B, D, F, I]
[B, D, F, J]
[B, D, F, K]
[B, D, G, H]
[B, D, G, I]
[B, D, G, J]
[B, D, G, K]
[B, E, F, H]
[B, E, F, I]
[B, E, F, J]
[B, E, F, K]
[B, E, G, H]
[B, E, G, I]
[B, E, G, J]
[B, E, G, K]
cartesianProductSize:48
rs.size:48
A=C=F=H
A=C=F=I
A=C=F=J
A=C=F=K
A=C=G=H
A=C=G=I
A=C=G=J
A=C=G=K
A=D=F=H
A=D=F=I
A=D=F=J
A=D=F=K
A=D=G=H
A=D=G=I
A=D=G=J
A=D=G=K
A=E=F=H
A=E=F=I
A=E=F=J
A=E=F=K
A=E=G=H
A=E=G=I
A=E=G=J
A=E=G=K
B=C=F=H
B=C=F=I
B=C=F=J
B=C=F=K
B=C=G=H
B=C=G=I
B=C=G=J
B=C=G=K
B=D=F=H
B=D=F=I
B=D=F=J
B=D=F=K
B=D=G=H
B=D=G=I
B=D=G=J
B=D=G=K
B=E=F=H
B=E=F=I
B=E=F=J
B=E=F=K
B=E=G=H
B=E=G=I
B=E=G=J
B=E=G=K

 

 

 

guava 的 Sets 和Lists 都提供了笛卡尔积的计算能力。但是Sets和Lists的cartesianProduct()方法是有区别的，Sets的笛卡尔积是对集合进行计算，其中计算的维度不允许由重复元素；Lists的笛卡尔积对list（列表）计算，其中计算的维度运行有重复元素。具体的功能可以参考他们的API文档。

Sets其实还提供了集合的并集、差集等一系列的集合操作。

import org.apache.commons.lang3.StringUtils;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

import java.util.List;
import java.util.Set;

/**
 * @ClassName: TestAll
 * @author kanpiaoxue
 * @version 1.0
 * @CreateTime: 2019/04/03 17:54:27
 */
public class TestAll {

    /**
     *
     * @param args
     * @author kanpiaoxue
     * @CreateTime: 2019/04/03 17:54:27
     */
    public static void main(String[] args) {
        // guava 的 Sets 提供了笛卡尔积的计算能力。 它其实还提供了集合的并集、差集等一系列的集合操作。
        Set<List<Object>> rs = Sets.cartesianProduct(ImmutableList.of(ImmutableSet.of(1, 2),
                ImmutableSet.of("A", "B", "C"), ImmutableSet.of("e", "f", "g")));
        rs.forEach(System.out::println);

        System.out.println(StringUtils.repeat("=", 100));

        rs = Sets.cartesianProduct(Lists.newArrayList(Sets.newLinkedHashSet(Lists.newArrayList(1, 2)),
                Sets.newLinkedHashSet(Lists.newArrayList("A", "B", "C")),
                Sets.newLinkedHashSet(Lists.newArrayList("e", "f"))));

        rs.forEach(System.out::println);
    }

}

 

输出结果：

[1, A, e]
[1, A, f]
[1, A, g]
[1, B, e]
[1, B, f]
[1, B, g]
[1, C, e]
[1, C, f]
[1, C, g]
[2, A, e]
[2, A, f]
[2, A, g]
[2, B, e]
[2, B, f]
[2, B, g]
[2, C, e]
[2, C, f]
[2, C, g]
==========================================================================
[1, A, e]
[1, A, f]
[1, B, e]
[1, B, f]
[1, C, e]
[1, C, f]
[2, A, e]
[2, A, f]
[2, B, e]
[2, B, f]
[2, C, e]
[2, C, f]

 

 

分享到：
| curl的基本用法
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    html + js +vue实现商品sku 笛卡尔积

    以下是一个简单的示例： ```javascript const colors = ['red', 'blue']; const sizes = ['S', 'M', 'L']; function cartesianProduct(arrays) { let result = [[]]; for (let arr of arrays) { result = ...

    Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

    Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例 Java语言中实现未知维度集合的笛卡尔积算法是数据处理和分析中的一个重要问题。本文将主要介绍Java基于递归和循环两种方式实现未知维度集合的笛卡尔...

    cartesian-product-sas:SAS中的笛卡尔积

    在SAS编程环境中，笛卡尔积（Cartesian Product）是一个重要的概念，特别是在处理数据集连接时。笛卡尔积是指从两个或多个数据集中取出每一对元素进行组合，形成一个新的数据集，新数据集中每一条记录都是原数据集中...

    前端开源库-cartesian-product

    3. **API设计**：提供简洁易用的API接口，如`cartesianProduct(arrays)`，使得开发者可以快速集成到项目中。 4. **兼容性**：考虑到前端开发的多样性，该库可能兼容各种现代浏览器和Node.js环境。 5. **示例与文档**...

    笛卡尔乘积判断

    class CartesianProduct { public static List, char&gt;&gt; ComputeCartesianProduct(List&lt;int&gt; A, List&lt;char&gt; B) { List, char&gt;&gt; result = new List, char&gt;&gt;(); foreach (int a in A) { foreach (char b in B) {...

    .net C# 实现任意List的笛卡尔乘积算法代码

    在给定的代码示例中，我们看到一个名为`CartesianProduct`的方法，这个方法可以计算任意数量的`List&lt;T&gt;`类型的集合的笛卡尔积。这个方法位于名为`算法`的静态类中，并且接受一个类型为`List&lt;List&lt;T&gt;&gt;`的参数，其中`T...

    数据库系统原理课件：作业讲评 2_4_1ppt.ppt

    其中涉及到的关系代数操作主要包括选择（Selection）、投影（Projection）、并集（Union）、差集（Difference）以及笛卡尔积（Cartesian Product）等。 1. 选择（Selection）：例如，`model( бspeed&gt;3.00 (PC) )` ...

    数据库系统概论第四版课后题

    - **关系操作集合**：主要包括选择（Select）、投影（Project）、并（Union）、差（Difference）、笛卡尔积（Cartesian Product）等基本操作，以及更复杂的连接（Join）、除法（Division）等。 - **关系完整性约束...

    数据库原理与程序设计孙杰第2章关系数据库系统.ppt

    2. **笛卡尔积（Cartesian Product）**：n个域的笛卡尔积是由这些域中所有可能的值对组成的集合。在关系模型中，笛卡尔积可以看作是一个未筛选的二维表，其中每一行代表一个元组，每一列代表一个属性。 3. **元组...

    数据库系统大题.doc

    - 笛卡尔积（Cartesian Product）：两个关系的笛卡尔积是将它们的所有记录进行一对一的组合。 - 分区（Division）：在SQL中，用除法操作表示，用于找出满足特定条件的所有记录的子集。 6. **数据库设计原则**： ...

    查询树的优化PPT学习教案.pptx

    - **交换率**：连接操作（JOIN）和笛卡尔积（CARTESIAN PRODUCT）可以互换位置，但连接条件也要相应调整。 - **结合率**：多个连接操作可以合并，连接条件也可以合并，以减少计算量。 - **投影的串接定律**：多个...

    第6章21

    5. **笛卡尔积（Cartesian Product）**: 用×表示，将两个关系的每一行组合在一起。 6. **重命名（Rename）**: 用ρ表示，更改关系或列的名称。 **6.5 运算符优先级** 关系代数中运算符的优先级如下： 1. 最高...

    sql语法(oracle,mysql,sqlserver)

    #### 笛卡尔积 (Cartesian Product) 笛卡尔积是两个或多个表的所有可能组合的结果。如果表A有m行，表B有n行，则笛卡尔积会产生m * n行结果。这种情况下，每个表A的行都会与表B的所有行进行配对。 **示例：** 假设...

    数据库课件总结：DataBase Chapter Two Outline.docx

    - **笛卡尔积(Cartesian Product)**: 将两个关系的所有可能组合生成一个新的关系。记作 _r × s_。 - 示例: 计算顾客与产品之间的所有可能配对。 - **重命名(Rename)**: 为关系或其属性提供新的名称。记作 _ρ(x)(E...

    Python-pireal关系代数的教育工具

    2. **基本操作**：工具可能支持基本的关系代数运算，如选择（Selection）、投影（Projection）、并集（Union）、差集（Difference）、笛卡尔积（Cartesian Product）、连接（Join）等。 3. **复合操作**：除了基础...

    数据库系统概论第五版课后习题答案王珊版.pdf

    - 并（Union）、差（Difference）、笛卡尔积（Cartesian Product）、投影（Projection）和选择（Selection）是关系代数的基本运算。 - 交（Intersection）、连接（Join）和除（Division）等操作可以通过这些基本...

    数据库教程

    关系数据库支持多种操作，如选择（Select）、投影（Project）、并（Union）、差（Difference）、笛卡尔积（Cartesian Product）等。这些操作允许我们从数据库中提取、修改或组合信息。例如，选择操作用于根据特定...

    SQL SERVER

    在SQL Server中，当两个表进行连接时，如果未指定任何连接条件，则会产生笛卡尔积（Cartesian Product），即第一个表的每一行都会与第二个表的所有行进行配对。 **示例**： ```sql SELECT student.*, sc.* FROM ...

    关系数据库标准语言SQL练习题.doc

    - 并（UNION）、差（EXCEPT）、选择（SELECT）、投影（PROJECT）和笛卡尔积（CARTESIAN PRODUCT）被认为是关系代数中的基本操作。这些操作可以帮助我们理解和实现SQL中的各种查询需求。 ### SQL语言的具体应用 1....

Magicbox
Global site tag (gtag.js) - Google Analytics