关于多个数组的笛卡尔积计算示例-查看文章

关于多个数组的笛卡尔积计算示例

发表于:2017-11-01 23:00:14 分类:JAVA 阅读:526次

image

用了一整天时间。

参考博文:递归和循环两种方式实现未知维度集合的笛卡尔积

什么是笛卡尔积? 在数学中,两个集合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<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;
    }
}



关键词:笛卡尔积


验证码: