Java实现笛卡尔积算法-递归

电玩女神 2022-12-06 01:12 426阅读 0赞

import java.util.ArrayList;
    import java.util.List;
    
    public class Test{
    	
    	public static void main(String[] args) {
    		List<String> list1 = new ArrayList<String>();
            list1.add("蓝色");
            list1.add("绿色");
            List<String> list2 = new ArrayList<String>();
            list2.add("X");
            list2.add("XL");
            list2.add("XXL");
            List<List<String>> dimValue = new ArrayList<List<String>>();
            dimValue.add(list1);
            dimValue.add(list2);
    
            // 递归实现笛卡尔积
            Test s=new Test();
            List<List<String>> res = s.descartes(dimValue);
            System.out.println("递归实现笛卡尔乘积: 共 " + res.size() + " 个结果");
            for (List<String> list : res) {
                for (String string : list) {
                    System.out.print(string + " ");
                }
                System.out.println();	
            }
    	}
    
    	public List<List<String>> descartes(List<List<String>> dimValue) {
            List<List<String>> res = new ArrayList<>();
            if (dimValue == null || dimValue.size() == 0)
                return res;
            backtrace(dimValue, 0, res, new ArrayList<>());
            return res;
    
        }
    
        /**
         * 递归回溯法求解
         *
         * @param dimValue 原始数据集合
         * @param index 当前执行的集合索引
         * @param result 结果集合
         * @param curList 当前的单个结果集
         */
        private void backtrace(List<List<String>> dimValue, int index, List<List<String>> result, List<String> curList) {
            if (curList.size() == dimValue.size()){
            	result.add(new ArrayList<>(curList));
            }else{
            	for(int j=0;j<dimValue.get(index).size();j++){
            		curList.add(dimValue.get(index).get(j));
            		backtrace(dimValue, index+1, result, curList);
            		curList.remove(curList.size() - 1);
            	}
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70]: /images/20221123/3bf0adc22a0c4efba1ac7e3f2f3bffee.png