笛卡尔积：笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员 [1] 。
进制转换： 进制转换是人们利用符号来计数的方法。进制转换由一组数码符号和两个基本因素“基数”与“位权”构成。基数是指，进位计数制中所采用的数码（数制中用来表示“量”的符号）的个数。位权是指，进位制中每一固定位置对应的单位值。
例如：十进制快速转换十六进制
103 = (6 * 16) + 7 = 0x67
22 = (1 * 16) + 6 = 0x16
54 = (3 * 16) + 6 = 0x36
255 = (15* 16) + 15 = 0xff
999 = (62 * 16) + 7 ~ 0x7
62= (3 * 16) + 14 ~ 0xe
= 3 ~ 0x3
= 0x3e7
9999= (624 * 16) + 15 ~ 0xF
624= (39*16) + 0 ~ 0x0
39= (2* 16) + 7 ~ 0x7
2= 2 ~ 0x2
= 0x270f
1980= (123 * 16) + 12 ~ 0xc
123= (7 * 16) + 11 ~ 0xb
7= 7 ~ 0x7
= 0x7bc
直接上代码
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
public class DescartesTest {
public static void main(String[] args) {
// 测试数据
Object[][] src = {{10,11,12},{20,21,22,23},{31,32},{10,11,12},{20,21,22,23},{31,32},
{10,11,12},{20,21,22,23},{31,32},{20,21,22,23},{31,32},{10,11,12},{20,21,22,23}};
// 测试使用jdk8的reduce方式计算笛卡尔积
long start = System.currentTimeMillis();
Object[] objects = descartesByStream(src);
System.out.println("reduce计算耗时："+(System.currentTimeMillis()-start)+" ms");
System.out.println("结果集长度："+objects.length);
// 测试采用数值进制转换算法计算笛卡尔积
start = System.currentTimeMillis();
Object[][] objects1 = descartesBySimple(src);
System.out.println("进制转换计算耗时："+(System.currentTimeMillis()-start)+" ms");
System.out.println("结果集长度："+objects.length);
}
/**
* 采用jdk8的新特性，stream的reduce方法实现笛卡尔积计算
* 该算法的计算方式依次两两相乘，其中给一个乘数集合要么是源数据的首个数组，要么是上次计算的结果集
* 该算法真是计算较为复杂，对资源消耗较高
* @param src 源数据，一个不定长的二维数组
* @return 计算结果，每一个组合采用list存储
*/
public static Object[] descartesByStream(Object[]... src){
return Stream.of(src).reduce((acc, item) -> {
// 用于保存当前已经计算的组合集合，该list中元素是已经计算的组合
ArrayList<Object> result = new ArrayList<>();
// 循环计算新的组合，进行集合A和集合B的笛卡尔积（A*B）
// acc 是本次计算之前已经完成计算的组合集合或者源数据中的第一个数组，为计算公式中的A
for (Object a : acc) {
// item 为本次计算的目标数组，为计算公式中的B
for (Object b : item) {
// a 可能是首个数组中的元素也可能是已计算的组合
// 如果 a 为List，则表示该元素为已经计算的组合，直接全部添加到新的组合中；
// 否则为首个数组的中的元素，进行单个元素添加
ArrayList<Object> temp = new ArrayList<>();
if(a instanceof List) {
temp.addAll((List) a);
}else {
temp.add(a);
}
// 向本次计算的组合中添加新元素
temp.add(b);
// 保存本次计算组合
result.add(temp);
}
}
// 将本次计算的所有组合返回，用于下次计算或者直接返回
return result.toArray();
}).get();
}
/**
* 采用进制转换算法实现笛卡尔积计算
* 该算法有一个特点就是语言限制，可以轻易的采用任何语言实现
*
* 其实我们经常使用的数字进制就是一个特殊的笛卡尔积
* 比如任意一个3位10进制数据，就是由三个相同数组{0,1,2,3,4,5,6,7,8,9}的笛卡尔积中的一个元素
* 任意进制数值之间的转换，可以通过取余计算指定位的值，
* 如果将上面的数字改为其他字符，将该值作为数组索引，也就可以转换其他的进制数字
* 那么，在计算普通的笛卡尔积的时候，可以将目标笛卡尔积看成一个混合进制的数字，
* 然后计算每一位的数组索引，取值填充到集合中，也就可以迅速计算笛卡尔积了
*
* 由于这种算法中的结果集中的任意两个元素之间计算并没有什么关联，所以还可以并行计算
* @param src
* @return
*/
public static Object[][] descartesBySimple(Object[]... src){
// 根据传入数据计算结果集长度
int resultLength = 1;
for (Object[] aSrc : src) {
resultLength *= aSrc.length;
}
// 初始化结果集
Object[][] result = new Object[resultLength][src.length];
// 核心算法
// 采用数据进制转换算法计算出组合中每一个位的索引值
// 然后在对应的数组中取值并填充到组合中
for (int i = 0; i < resultLength; i++) {
int tmp = i;
// 进制转换算法
for (int j = src.length-1; j >=0; j--) {
int t = tmp/src[j].length;
result[i][j] = src[j][tmp- t * src[j].length];
tmp = t;
}
}
return result;
}
}
以上测试代码运行结果为：
reduce计算耗时：1392 ms
结果集长度：1327104
进制转换计算耗时：334 ms
结果集长度：1327104
全部评论