1.1 文档目的本文档对M源代码进行完整说明包含程序功能、数据结构、核心逻辑、代码注释、缺陷分析、运行现象、源码全量带注释版本供开发调试、课程实验查阅使用。1.2 开发环境开发语言Java 8依赖集合类ArrayList、HashMap、List、Map包路径com1.3 整体功能本程序在求解一个集合的子集的过程中需要首先对集合进行从小到大排序然后通过递归迭代求出所有子集。1.4 程序缺点求子集的前期是需要先对数进行排序然后才能算出每个子集中包含的数字。不能在不排序的情况下求出所有子集。感兴趣都可以自己研究下 。2 数据结构设计全局共享容器MapString, ListListInteger map三个固定 Key 承担不同存储职责表格Key 名称存储结构作用说明listListListInteger原始数据源仅存放 1 个一维数组即输入数字集合[1,4,6,7,8]listsListListInteger全局结果集存放所有生成完成的递增子序列prevListListInteger缓存上一轮递归产出的子序列用于本轮拼接生成更长子序列辅助局部变量说明list从map.get(list)取出原始一维数字数组listPrev接收prev缓存集合区分首次递归 / 迭代扩展递归u临时集合存储本轮新生成的加长子序列递归结束后赋值给prev3 核心方法说明3.1 递归方法 getR方法签名java运行public static MapString, ListListInteger getR(MapString, ListListInteger map)入参map全局数据容器包含原始数据、结果集、上一轮子序列缓存返回值传入的原Map对象引用传递内部数据已被递归修改分支逻辑拆分分支 1prev 为空首次递归入口遍历原始数组每个数字生成长度为 1 的单元素子序列所有单元素序列存入全局结果lists将单元素序列存入临时集合u赋值给prev递归调用自身进入长序列生成逻辑。分支 2prev 存在数据扩展更长子序列遍历上一轮全部短子序列复制当前短序列遍历原始数组所有数字判断序列末尾数字 当前遍历数字满足则拼接新序列新序列存入全局结果集同时存入临时集合u更新prev为本轮拼接出的长序列递归调用自身继续生成更长子序列。4 Main 主方法执行流程初始化空集合、存储 Map 容器填充原始数字数组[1,4,6,7,8]封装为二维集合存入list键初始化空结果集lists、空缓存prev放入 Map调用递归方法getR(map)开始生成子序列取出递归后的结果集手动新增一个空一维集合插入结果列表打印修改后的结果集合5 完整代码如下java运行package com; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 递归生成严格递增子序列程序 * 功能基于有序数字数组递归构造全部严格递增子序列 * 缺陷无递归终止条件无限递归触发栈溢出StackOverflowError */ public class MyProject { /** * 递归核心函数循环扩展生成递增子序列 * param map 全局数据存储容器 * keylist原始一维数字数组二维包装 * keylists所有递增子序列总结果集 * keyprev上一轮生成的子序列缓存用于拼接更长序列 * return 修改完成数据后的map引用对象 */ public static MapString,ListListInteger getR( MapString,ListListInteger map){ // 获取原始数字一维数组 [1,4,6,7,8] ListInteger listmap.get(list).get(0); // 获取全局结果集合存放所有子序列 ListListInteger listsmap.get(lists); // 定义变量接收上一轮子序列缓存 ListListInteger listPrevnew ArrayList(); // 若prev缓存存在数据则赋值给临时变量 if(map.get(prev).size()0){ listPrevmap.get(prev); } // 判断存在上一轮生成的子序列需要拼接更长序列 if(listPrev!nulllistPrev.size()0){ // 空分支无任何处理逻辑冗余代码 if(listPrev.size()1){ }else{ // u存储本轮新生成的加长子序列作为下一轮prev缓存 ListListInteger unew ArrayList(); // 遍历上一轮所有短子序列 for(int i0;ilistPrev.size();i){ // 复制当前子序列防止修改原缓存集合 ListInteger lnew ArrayList(); l.addAll(listPrev.get(i)); // 遍历原始数组所有数字尝试尾部追加 for(int j0;jlist.size();j){ // 严格递增判定序列最后一位小于待追加数字 if(l.get(l.size()-1)list.get(j)){ // 构建新子序列 ListInteger list1new ArrayList(); list1.addAll(l); // 追加更大数值生成长度1的递增子序列 list1.add(list.get(j)); // 存入全局结果集 lists.add(list1); // 存入本轮临时集合用于下一轮递归 u.add(list1); } } // 同步更新map内的结果集 map.put(lists, lists); } // 将本轮生成序列设置为下一轮的prev缓存 map.put(prev, u); // 递归调用继续生成更长子序列 getR(map); } }else{ // 首次递归prev缓存为空生成长度为1的单元素子序列 ListListInteger unew ArrayList(); // 遍历原始数组每一个数字 for(int i0;ilist.size();i){ ListInteger lnew ArrayList(); l.add(list.get(i)); // 存入全局结果 lists.add(l); // 存入临时集合作为下一轮prev数据 u.add(l); } // 更新map缓存与结果集 map.put(prev, u); map.put(lists,lists); // 递归进入长序列扩展逻辑 getR(map); } // 返回数据容器 return map; } public static void main(String[] args) { // 原始数字一维数组 ListInteger lnew ArrayList(); // 全局数据存储Map MapString,ListListInteger mapnew HashMap(); // 二维包装容器用于存放原始一维数组 ListListInteger mnew ArrayList(); // 初始化全局子序列结果集合 ListListInteger nnew ArrayList(); // 初始化prev空缓存集合 ListListInteger unew ArrayList(); // 将空结果集、空前置缓存存入map map.put(lists,n); map.put(prev, u); // 填充待处理有序数字 l.add(1); l.add(4); l.add(6); l.add(7); l.add(8); // 一维数组包装进二维集合 m.add(l); // 原始数据源存入map map.put(list, m); // 调用递归生成所有递增子序列会无限递归栈溢出 mapgetR(map); // 取出递归后的结果集合代码无法执行到此处 ListListInteger lists1map.get(lists); // 创建空一维列表 ListInteger l1new ArrayListInteger(); // 将空列表插入结果集合首位 lists1.add(l1); // 覆盖map内的结果集 map.put(lists, lists1); // 控制台打印输出代码无法执行到此处 System.out.println(lists1); } }
使用Java编写一个求集合所有子集的代码
1.1 文档目的本文档对M源代码进行完整说明包含程序功能、数据结构、核心逻辑、代码注释、缺陷分析、运行现象、源码全量带注释版本供开发调试、课程实验查阅使用。1.2 开发环境开发语言Java 8依赖集合类ArrayList、HashMap、List、Map包路径com1.3 整体功能本程序在求解一个集合的子集的过程中需要首先对集合进行从小到大排序然后通过递归迭代求出所有子集。1.4 程序缺点求子集的前期是需要先对数进行排序然后才能算出每个子集中包含的数字。不能在不排序的情况下求出所有子集。感兴趣都可以自己研究下 。2 数据结构设计全局共享容器MapString, ListListInteger map三个固定 Key 承担不同存储职责表格Key 名称存储结构作用说明listListListInteger原始数据源仅存放 1 个一维数组即输入数字集合[1,4,6,7,8]listsListListInteger全局结果集存放所有生成完成的递增子序列prevListListInteger缓存上一轮递归产出的子序列用于本轮拼接生成更长子序列辅助局部变量说明list从map.get(list)取出原始一维数字数组listPrev接收prev缓存集合区分首次递归 / 迭代扩展递归u临时集合存储本轮新生成的加长子序列递归结束后赋值给prev3 核心方法说明3.1 递归方法 getR方法签名java运行public static MapString, ListListInteger getR(MapString, ListListInteger map)入参map全局数据容器包含原始数据、结果集、上一轮子序列缓存返回值传入的原Map对象引用传递内部数据已被递归修改分支逻辑拆分分支 1prev 为空首次递归入口遍历原始数组每个数字生成长度为 1 的单元素子序列所有单元素序列存入全局结果lists将单元素序列存入临时集合u赋值给prev递归调用自身进入长序列生成逻辑。分支 2prev 存在数据扩展更长子序列遍历上一轮全部短子序列复制当前短序列遍历原始数组所有数字判断序列末尾数字 当前遍历数字满足则拼接新序列新序列存入全局结果集同时存入临时集合u更新prev为本轮拼接出的长序列递归调用自身继续生成更长子序列。4 Main 主方法执行流程初始化空集合、存储 Map 容器填充原始数字数组[1,4,6,7,8]封装为二维集合存入list键初始化空结果集lists、空缓存prev放入 Map调用递归方法getR(map)开始生成子序列取出递归后的结果集手动新增一个空一维集合插入结果列表打印修改后的结果集合5 完整代码如下java运行package com; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 递归生成严格递增子序列程序 * 功能基于有序数字数组递归构造全部严格递增子序列 * 缺陷无递归终止条件无限递归触发栈溢出StackOverflowError */ public class MyProject { /** * 递归核心函数循环扩展生成递增子序列 * param map 全局数据存储容器 * keylist原始一维数字数组二维包装 * keylists所有递增子序列总结果集 * keyprev上一轮生成的子序列缓存用于拼接更长序列 * return 修改完成数据后的map引用对象 */ public static MapString,ListListInteger getR( MapString,ListListInteger map){ // 获取原始数字一维数组 [1,4,6,7,8] ListInteger listmap.get(list).get(0); // 获取全局结果集合存放所有子序列 ListListInteger listsmap.get(lists); // 定义变量接收上一轮子序列缓存 ListListInteger listPrevnew ArrayList(); // 若prev缓存存在数据则赋值给临时变量 if(map.get(prev).size()0){ listPrevmap.get(prev); } // 判断存在上一轮生成的子序列需要拼接更长序列 if(listPrev!nulllistPrev.size()0){ // 空分支无任何处理逻辑冗余代码 if(listPrev.size()1){ }else{ // u存储本轮新生成的加长子序列作为下一轮prev缓存 ListListInteger unew ArrayList(); // 遍历上一轮所有短子序列 for(int i0;ilistPrev.size();i){ // 复制当前子序列防止修改原缓存集合 ListInteger lnew ArrayList(); l.addAll(listPrev.get(i)); // 遍历原始数组所有数字尝试尾部追加 for(int j0;jlist.size();j){ // 严格递增判定序列最后一位小于待追加数字 if(l.get(l.size()-1)list.get(j)){ // 构建新子序列 ListInteger list1new ArrayList(); list1.addAll(l); // 追加更大数值生成长度1的递增子序列 list1.add(list.get(j)); // 存入全局结果集 lists.add(list1); // 存入本轮临时集合用于下一轮递归 u.add(list1); } } // 同步更新map内的结果集 map.put(lists, lists); } // 将本轮生成序列设置为下一轮的prev缓存 map.put(prev, u); // 递归调用继续生成更长子序列 getR(map); } }else{ // 首次递归prev缓存为空生成长度为1的单元素子序列 ListListInteger unew ArrayList(); // 遍历原始数组每一个数字 for(int i0;ilist.size();i){ ListInteger lnew ArrayList(); l.add(list.get(i)); // 存入全局结果 lists.add(l); // 存入临时集合作为下一轮prev数据 u.add(l); } // 更新map缓存与结果集 map.put(prev, u); map.put(lists,lists); // 递归进入长序列扩展逻辑 getR(map); } // 返回数据容器 return map; } public static void main(String[] args) { // 原始数字一维数组 ListInteger lnew ArrayList(); // 全局数据存储Map MapString,ListListInteger mapnew HashMap(); // 二维包装容器用于存放原始一维数组 ListListInteger mnew ArrayList(); // 初始化全局子序列结果集合 ListListInteger nnew ArrayList(); // 初始化prev空缓存集合 ListListInteger unew ArrayList(); // 将空结果集、空前置缓存存入map map.put(lists,n); map.put(prev, u); // 填充待处理有序数字 l.add(1); l.add(4); l.add(6); l.add(7); l.add(8); // 一维数组包装进二维集合 m.add(l); // 原始数据源存入map map.put(list, m); // 调用递归生成所有递增子序列会无限递归栈溢出 mapgetR(map); // 取出递归后的结果集合代码无法执行到此处 ListListInteger lists1map.get(lists); // 创建空一维列表 ListInteger l1new ArrayListInteger(); // 将空列表插入结果集合首位 lists1.add(l1); // 覆盖map内的结果集 map.put(lists, lists1); // 控制台打印输出代码无法执行到此处 System.out.println(lists1); } }
