给定一个集合（字符数组），打印出它的所有子集

/** * 给定一个集合（字符数组），打印出它的所有子集 * @param set - 给定的集合（字符数组） */ public void showAllSubset(char[] set) { boolean[] flags = new boolean[set.length]; //若第i个元素为true，则表示集合中第i个元素被选中 int count = 0; //记录集合中被选中元素的总数 int cur = 0; //当前正在考察的集合中元素的位置 System.out.println("{ Φ }"); //首先输出空集 for(int i=1; i<=set.length; i++) { //寻找子集的时候，长度依次递增，即i=2表示寻找所有长度为2的子集 //每次刚开始寻找长度为i的子集的时候，做一些初始化操作 Arrays.fill(flags, false); //flags数组初始化为false，表示集合中没有任何元素被选中 count = 0; //被选中元素总数清零 cur = 0; //准备从第一个元素开始考察 while(true) { //开始寻找所有长度为i的子集 if(count==i) { //如果已经选中了i个元素，则表明已经找到了一个子集 printSubset(flags, set); //打印出这个子集 //如果当前元素已超出数组范围，并且距离子集的第一个元素的距离为i //则表明这是当前长度下最后一个子集，不必再继续寻找了，跳出循环 if(cur==set.length && cur-findFirstFlag(flags)==i) { break; }else { //反之，则回溯。即清除最后一个选中标志，选中总数减1，准备考察后面的元素 flags[cur-1] = false; count--; } //如果当前元素的位置不正确，则回溯 //所谓的位置不正确，举个简单的例子，比如原集合有5个元素，正在寻找长度为3的子集 //已经选中了1个元素，在考察第2个元素的时候，其位置不能是最后一个元素，因为这样的话就无法找到第3个元素 //另外，当前元素的位置超出了原集合的范围，显然也是不正确的 }else if(cur+i == set.length+count+1) { cur = findLastFlag(flags); //找到已选中的最后一个元素 flags[cur++] = false; //将其标为未选中，并准备考察它下一个元素 count--; }else { //若无特殊情况，则选中当前元素，准备考察下一个元素 flags[cur++] = true; count++; } } } } /** * 辅助函数，打印出某个集合的子集 * @param flags - 标识数组，标明了集合中都有哪些元素被选入子集中 * @param set - 原集合 */ private void printSubset(boolean[] flags, char[] set) { System.out.print("{ "); boolean firstFlag = true; for(int i=0; i<set.length; i++) { if(flags[i]) { if(firstFlag) { System.out.print(set[i]); firstFlag = false; }else { System.out.print(", " + set[i]); } } } System.out.println(" }"); } /** * 辅助函数，找到原集合中最后一个被选中元素的下标 * @param flags - 标识数组，标明了集合中都有哪些元素被选入子集中 * @return 最后一个被选中元素的下标 */ private int findLastFlag(boolean[] flags) { int i = -2; for(int j=flags.length-1; j>=0; j--) { if(flags[j]) { i = j; break; } } return i; } /** * 辅助函数，找到原集合中第一个被选中元素的下标 * @param flags - 标识数组，标明了集合中都有哪些元素被选入子集中 * @return 第一个被选中元素的下标 */ private int findFirstFlag(boolean[] flags) { int i = -1; for(int j=0; j<flags.length; j++) { if(flags[j]) { i = j; break; } } return i; }

根据整数分解为二进制1，0串来寻找子集。例如一个含有3个元素的集合，他的非空子集共有2的3次方减1，即7个。因此我们做一个从1到7的循环，将这些整数分解为2进制1，0串，根据其中1的位置来确定子集。

/** * 给定一个集合（字符数组），打印出它的所有子集 * @param set - 给定的集合（字符数组） */ public void showAllSubset(char[] set) { int[] flags = new int[set.length]; System.out.println("{ }"); for(int i=1; i<(1<<set.length); i++) { calculateFlags(set, flags, i); printSubset(flags, set); } } /** * 辅助函数，将一个整数分解为二进制的1，0串，凡是等于1的位置， * 即是我们挑选出来进入子集的元素 * @param set - 原集合 * @param flags - 标识数组，将选中进入子集的元素标识出来 * @param num - 分解为二进制1，0串后，用于计算标识数组的一个整数 */ private void calculateFlags(char[] set, int[] flags, int num){ for(int i=0; i<set.length; i++) { flags[i] = ((1<<i) & num) >> i; } } /** * 辅助函数，打印出某个集合的子集 * @param flags - 标识数组，标明了集合中都有哪些元素被选入子集中 * @param set - 原集合 */ private void printSubset(int[] flags, char[] set) { System.out.print("{ "); boolean firstFlag = true; for(int i=0; i<set.length; i++) { if(flags[i]==1) { if(firstFlag) { System.out.print(set[i]); firstFlag = false; }else { System.out.print(", " + set[i]); } } } System.out.println(" }"); }

最后

以上就是英俊期待最近收集整理的关于给定一个集合（字符数组），打印出它的所有子集的全部内容，更多相关给定一个集合（字符数组），打印出它内容请搜索靠谱客的其他文章。