关于多个数组的笛卡尔积计算示例
发表于:2017-11-01 23:00:14 分类:JAVA 阅读:526次
用了一整天时间。
什么是笛卡尔积?
在数学中,两个集合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
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(); } } }
我的应用:
要求输入一个数组,求出它的元素任意相加的结果为输入结果的所有组合。(如标题图)
package test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * Created by ersredma on 2017/11/1. */ public class CartesianProductTest { public static int subIndex; public static int[] arrays; public static void main(String[] args){ System.out.println("请输入大于0的正整数数组,以,隔开:"); Scanner sc=new Scanner(System.in); String[] ss= sc.next().split(","); arrays=new int[ss.length]; for(int i=0;i<ss.length;i++){ arrays[i]=Integer.parseInt(ss[i]); if(arrays[i]<=0){ System.out.println("输入有误,请重新开始!"); } } System.out.println("请输入结果:"); int res=sc.nextInt(); Arrays.sort(arrays); subIndex=-1; for(int i=arrays.length-1;i>=0;i--){ if(res>=arrays[i]){ subIndex=i; break; } } System.out.println(subIndex); if(subIndex<0){ System.out.println("无结果;"); return; } List conList=new ArrayList(); for(int i=subIndex;i>=0;i--){ List list=new ArrayList<Integer>(); list.add(0); int flag=arrays[i]; while(res>=flag){ list.add(flag); flag=flag+arrays[i]; } conList.add(list); } System.out.println(conList); List<String> reslist=resList(conList,res); for(int i=0;i<reslist.size();i++){ System.out.println(reslist.get(i)); } } //传入一个列表,列表中的每个元素为一个int列表。res为比较值。 //方法功能:列表中n个元素相加的和如果是res,就将当前相加用string表示存入结果 public static List resList(List<List> numList, int res){ int count=1; for(int i=0;i<numList.size();i++){ List l=(List)numList.get(i); count=count*l.size(); } String[] myResult = new String[count]; int itemLoopNum = 1; int loopPerItem = 1; int now = 1; for (List list : numList) { now *= list.size(); int index = 0; int currentSize = list.size(); itemLoopNum = count / now; loopPerItem = count / (itemLoopNum * currentSize); int myIndex = 0; for (Object str : 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的笛卡尔积 List<String> dcrResult = Arrays.asList(myResult); List<String> resList=new ArrayList<String>(); for(int i=0;i<dcrResult.size();i++){ String str=dcrResult.get(i); String[] strarr=str.split("\\+"); int sum=0; for(int j=0;j<strarr.length;j++){ int number=Integer.parseInt(strarr[j]); sum=sum+number; } if(sum==res){ String s=""; for(int j=0;j<strarr.length;j++){ int number=Integer.parseInt(strarr[j]); if(number>0){ if(number>arrays[subIndex-j]){ //s=s+arrays[subIndex-j]+"*"+number/arrays[subIndex-j]+"+"; int cou=number/arrays[subIndex-j]; while (cou>0){ s=s+arrays[subIndex-j]+"+"; cou--; } }else{ s=s+number+"+"; } } } s=s+"="+res; s=s.replace("+=","="); resList.add(s); } } return resList; } }
关键词:笛卡尔积