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

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

本文实例讲述了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> 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> dimValue, List> result, int layer, List&http://lt;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 list = new ArrayList(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 list = new ArrayList(curList);

list.add(dimValue.get(layer).get(i));

result.add(list);

}

}

}

}

/**

* 循环实现dimValue中的笛卡尔积，结果放在result中

* @param dimValue 原始数据

* @param result 结果数据

*/

private static void circulate (List> dimValue, List> result) {

int total = 1;

for (List list : dimValue) {

total *= list.size();

}

String[] myResult = new String[total];

int itemLoopNum = 1;

int loopPerItem = 1;

int now = 1;

for (List 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 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 list1 = new ArrayList();

list1.add("1");

list1.add("2");

List list2 = new ArrayList();

list2.add("a");

list2.add("b");

List list3 = new ArrayList();

list3.add("3");

list3.add("4");

list3.add("5");

List list4 = new ArrayList();

list4.add("c");

list4.add("d");

list4.add("e");

List> dimValue = new ArrayList>();

dimValue.add(list1);

dimValue.add(list2);

dimValue.add(list3);

dimValue.add(list4);

List> recursiveResult = new ArrayList>();

// 递归实现笛卡尔积

recursive(dimValue, recursiveResult, 0, new ArrayList());

System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果");

for (List list : recursiveResult) {

for (String string : list) {

System.out.print(string + " ");

}

System.out.println();

}

List> circulateResult = new ArrayList>();

circulate(dimValue, circulateResult);

System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果");

for (List 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

2http:// 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 olWOWDd

2 b 4 e

2 b 5 c

2 b 5 d

2 b 5 e

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。