优化：java递归实现笛卡尔积算法

太过爱你忘了你带给我的痛 2021-09-07 06:08 553阅读 0赞

笛卡尓积又称直积，表示为X×Y。

**举例：**集合A=\{a, b\}，集合B=\{0, 1, 2\}，则两个集合的笛卡尔积为\{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)\}。

**应用场景：**一个手机规格：型号note、pro，闪存4G、8G，内存64G、128G，配置标配、低配、高配。如果想保存这些规格信息（哪些卖完哪些没卖完），当然必须得到所有的组合信息。

**递归实现：**不多说了，直接撸代码，总共实现不到10行（这一套是博主自己想的，写之前没看那个已经被抄的不能再多的代码，看上去有点像，没办法递归只能这样）：

public static void main(String[] args) {
            List<List<String>> listData = new ArrayList<>();
            listData.add(Arrays.asList("note", "pro"));
            listData.add(Arrays.asList("4G", "8G"));
            listData.add(Arrays.asList("64", "128"));
            listData.add(Arrays.asList("标配", "低配", "高配"));
            List<List<String>> lisReturn = getDescartes(listData);
            System.out.println(lisReturn);
        }
    
        private static <T> List<List<T>> getDescartes(List<List<T>> list) {
            List<List<T>> returnList = new ArrayList<>();
            descartesRecursive(list, 0, returnList, new ArrayList<T>());
            return returnList;
        }
    
        /**
         * 递归实现
         * 原理：从原始list的0开始依次遍历到最后
         *
         * @param originalList 原始list
         * @param position     当前递归在原始list的position
         * @param returnList   返回结果
         * @param cacheList    临时保存的list
         */
        private static <T> void descartesRecursive(List<List<T>> originalList, int position, List<List<T>> returnList, List<T> cacheList) {
            List<T> originalItemList = originalList.get(position);
            for (int i = 0; i < originalItemList.size(); i++) {
                //最后一个复用cacheList，节省内存
                List<T> childCacheList = (i == originalItemList.size() - 1) ? cacheList : new ArrayList<>(cacheList);
                childCacheList.add(originalItemList.get(i));
                if (position == originalList.size() - 1) {//遍历到最后退出递归
                    returnList.add(childCacheList);
                    continue;
                }
                descartesRecursive(originalList, position + 1, returnList, childCacheList);
            }
        }

这种方式稍微消耗内存，但效率绝对是最高的，当然你也可以不使用递归实现。

**不用递归的实现：**很简单就描述一下：先计算出总共有多少种，比如上面的2x2x2x3=24种，直接for i<24，每次循环都根据i来计算出每一个规格的index（比如：i=3，规格的index应该是(0,0,1,0)）①，直接根据index索引取值即可。

①此处也也可以用一个长度为4的一维数组保存index，每次for自加1并判断是否需要进一位即可，稍微好一点点