Java求数组所有子数组的两种方法
一个包含n个元素的集合,求它的所有子集。比如集合A= {1,2,3}, 它的所有子集是:
{ {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, @}(@表示空集)。
这种问题一般有两种思路,先说说第一种,递归。递归肯定要基于一个归纳法的思想,这个思想用到了二叉树的遍历,如下图所示:
可以这样理解这张图,从集合A的每个元素自身分析,它只有两种状态,或是某个子集的元素,或是不属于任何子集,所以求子集的过程就可以看成对每个元素进行“取舍”的过程。上图中,根结点是初始状态,叶子结点是终结状态,该状态下的8个叶子结点就表示集合A的8个子集。第i层(i=1,2,3…n)表示已对前面i-1层做了取舍,所以这里可以用递归了。整个过程其实就是对二叉树的先序遍历。
代码见方法getSonSet1。
还有一种思想比较巧妙,可以叫按位对应法。如集合A={a,b,c},对于任意一个元素,在每个子集中,要么存在,要么不存在。
映射为子集:
(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)
观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数与集合映射00…00 ~ 11…11(1表示有,0表示无,反之亦可),通过该整型数逐次增可遍历获取所有的数,即获取集合的相应子集。
实现代码见方法getSonSet2
import java.util.ArrayList;
import java.util.List;
public class SonSet {
public static void main(String[] args){
int[] arr={1,2,3};
List<Integer> aList=new ArrayList<Integer>();
List<Integer> bList=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++){
aList.add(arr[i]);
}
getSonSet1(0,aList,bList); //方法1,递归法
System.out.println("----数组arr公用,分割线-----");
getSonSet2(arr,arr.length); //方法2,按位对应法
}
/*
* 递归法
*/
public static void getSonSet1(int i,List<Integer> aList,List<Integer> bList){
if(i>aList.size()-1){
if(bList.size()<=0){
System.out.print("@");
}else {
/*for(int v:bList){
System.out.print(v+",");//可以直接用这种方法输出bList数组里所有值,但是每个子数组最后就会带逗号
}*/
System.out.print(bList.get(0));
for(int m=1;m<bList.size();m++){
System.out.print(","+bList.get(m));
}
}
System.out.println();
}else {
bList.add(aList.get(i));
getSonSet1(i+1, aList, bList);
int bLen=bList.size();
bList.remove(bLen-1);
getSonSet1(i+1, aList, bList);
}
}
/*
*按位对应法。
*/
private static void getSonSet2(int[] arr, int length) {
int mark=0;
int nEnd=1<<length;
boolean bNullSet=false;
for(mark=0;mark<nEnd;mark++){
bNullSet=true;
for(int i=0;i<length;i++){
if(((1<<i)&mark)!=0){//该位有元素输出
bNullSet=false;
System.out.print(arr[i]+",");
}
}
if(bNullSet){//空集合
System.out.print("@");
}
System.out.println();
}
}
}
- 1
运行结果:
1,2,3
1,2
1,3
1
2,3
2
3
@
----数组arr公用,分割线-----
@
1,
2,
1,2,
3,
1,3,
2,3,
1,2,3,
- 1