Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例
作者:buptdavid 时间:2021-07-19 04:41:18
本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积。分享给大家供大家参考,具体如下:
什么是笛卡尔积?
在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。
假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。
如何用程序算法实现笛卡尔积?
如果编程前已知集合的数量,通过程序的多次循环即可得出笛卡尔积。但是如果编程前不知道集合的数量,如何得到笛卡尔积哪?比如集合表示List < List<String>> list
;这个list在编程前list的数量是未知的。下面的代码使用递归和循环两种方法实现未知维度集合的笛卡尔积:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 循环和递归两种方式实现未知维度集合的笛卡尔积
* Created on 2015-05-22
* @author luweijie
*/
public class Descartes {
/**
* 递归实现dimValue中的笛卡尔积,结果放在result中
* @param dimValue 原始数据
* @param result 结果数据
* @param layer dimValue的层数
* @param curList 每次笛卡尔积的结果
*/
private static void recursive (List<List<String>> dimValue, List<List<String>> result, int layer, List<String> curList) {
if (layer < dimValue.size() - 1) {
if (dimValue.get(layer).size() == 0) {
recursive(dimValue, result, layer + 1, curList);
} else {
for (int i = 0; i < dimValue.get(layer).size(); i++) {
List<String> list = new ArrayList<String>(curList);
list.add(dimValue.get(layer).get(i));
recursive(dimValue, result, layer + 1, list);
}
}
} else if (layer == dimValue.size() - 1) {
if (dimValue.get(layer).size() == 0) {
result.add(curList);
} else {
for (int i = 0; i < dimValue.get(layer).size(); i++) {
List<String> list = new ArrayList<String>(curList);
list.add(dimValue.get(layer).get(i));
result.add(list);
}
}
}
}
/**
* 循环实现dimValue中的笛卡尔积,结果放在result中
* @param dimValue 原始数据
* @param result 结果数据
*/
private static void circulate (List<List<String>> dimValue, List<List<String>> result) {
int total = 1;
for (List<String> list : dimValue) {
total *= list.size();
}
String[] myResult = new String[total];
int itemLoopNum = 1;
int loopPerItem = 1;
int now = 1;
for (List<String> list : dimValue) {
now *= list.size();
int index = 0;
int currentSize = list.size();
itemLoopNum = total / now;
loopPerItem = total / (itemLoopNum * currentSize);
int myIndex = 0;
for (String string : list) {
for (int i = 0; i < loopPerItem; i++) {
if (myIndex == list.size()) {
myIndex = 0;
}
for (int j = 0; j < itemLoopNum; j++) {
myResult[index] = (myResult[index] == null? "" : myResult[index] + ",") + list.get(myIndex);
index++;
}
myIndex++;
}
}
}
List<String> stringResult = Arrays.asList(myResult);
for (String string : stringResult) {
String[] stringArray = string.split(",");
result.add(Arrays.asList(stringArray));
}
}
/**
* 程序入口
* @param args
*/
public static void main (String[] args) {
List<String> list1 = new ArrayList<String>();
list1.add("1");
list1.add("2");
List<String> list2 = new ArrayList<String>();
list2.add("a");
list2.add("b");
List<String> list3 = new ArrayList<String>();
list3.add("3");
list3.add("4");
list3.add("5");
List<String> list4 = new ArrayList<String>();
list4.add("c");
list4.add("d");
list4.add("e");
List<List<String>> dimValue = new ArrayList<List<String>>();
dimValue.add(list1);
dimValue.add(list2);
dimValue.add(list3);
dimValue.add(list4);
List<List<String>> recursiveResult = new ArrayList<List<String>>();
// 递归实现笛卡尔积
recursive(dimValue, recursiveResult, 0, new ArrayList<String>());
System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果");
for (List<String> list : recursiveResult) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
List<List<String>> circulateResult = new ArrayList<List<String>>();
circulate(dimValue, circulateResult);
System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果");
for (List<String> list : circulateResult) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
}
}
输出结果是:
递归实现笛卡尔乘积: 共 36 个结果
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e
循环实现笛卡尔乘积: 共 36 个结果
1 a 3 c
1 a 3 d
1 a 3 e
1 a 4 c
1 a 4 d
1 a 4 e
1 a 5 c
1 a 5 d
1 a 5 e
1 b 3 c
1 b 3 d
1 b 3 e
1 b 4 c
1 b 4 d
1 b 4 e
1 b 5 c
1 b 5 d
1 b 5 e
2 a 3 c
2 a 3 d
2 a 3 e
2 a 4 c
2 a 4 d
2 a 4 e
2 a 5 c
2 a 5 d
2 a 5 e
2 b 3 c
2 b 3 d
2 b 3 e
2 b 4 c
2 b 4 d
2 b 4 e
2 b 5 c
2 b 5 d
2 b 5 e
希望本文所述对大家java程序设计有所帮助。
来源:http://blog.csdn.net/buptdavid/article/details/45918647
标签:Java,笛卡尔积
0
投稿
猜你喜欢
Java Web实现简易图书管理系统
2023-12-17 21:48:34
Java编程用两个栈实现队列代码分享
2023-03-22 01:05:05
startActivityForResult和setResult案例详解
2023-09-15 19:13:33
struts2中使用注解配置Action方法详解
2023-08-30 00:01:25
springMVC自定义注解,用AOP来实现日志记录的方法
2023-11-29 13:58:53
spring cache注解@Cacheable缓存穿透详解
2023-12-23 13:41:25
SpringBoot结合JSR303对前端数据进行校验的示例代码
2022-09-15 03:22:55
详解java CountDownLatch和CyclicBarrier在内部实现和场景上的区别
2022-03-22 13:03:02
IDEA编译报错:Error:java:无效的源发行版:17的解决办法
2023-08-25 10:38:06
Java中保证线程顺序执行的操作代码
2023-05-14 17:36:46
Java图形用户界面设计(Swing)的介绍
2022-08-23 03:29:37
hibernate4基本配置方式详解
2023-03-11 11:07:43
使用Spring Boot Mybatis 搞反向工程的步骤
2022-05-15 06:54:35
Java中接口和抽象类的区别详解
2022-09-28 15:21:19
使用AOP的@Around后无返回值的解决
2023-11-24 13:04:09
Jenkins迁移job插件Job Import Plugin流程详解
2022-05-21 03:22:56
Java守护线程实例详解_动力节点Java学院整理
2023-03-29 08:14:30
剖析Java中线程编程的概念
2022-02-02 04:12:51
kill命令在Java应用中使用的注意事项小结
2023-11-11 13:01:55
Java等待唤醒机制线程通信原理解析
2022-03-31 00:37:21