Java求出一个给定集合的所有子集

原创
2016/06/15 16:08
阅读数 6.6K

思路:

        假设集合有4个元素{a,b,c,d},那么做一个for循环从0到15,每次输出一个子集。0(0000)表示空子集,1(0001)因为最低位为1,所以在集合四个元素中取第一个元素{a}作为一个子集,2(0010)因为次低位为1,所以在集合四个元素中取第二个元素{b}作为一个子集,3(0011)因为最低位和次低位都为1,所以在集合四个元素中取第一、第二个元素{a,b}作为一个子集......,依次类推15(1111)表示{a,b,c,d}。
再举个详细例子:
假设有集合{a,b,c},则:
迭代0到2^n-1==0到7
0(000):{}
1(001):{a}
2(010):{b}
3(011):{ab}
4(100):{c}
5(101):{a,c}
6(110):{b,c}
7(111):{a,b,c}


代码:

package demo16;

import java.util.HashSet;
import java.util.Set;

public class SubSet {
	public static void main(String[] args) {
		int[] set = new int[] { 1, 2 ,3};
		Set<Set<Integer>> result = getSubSet(set); // 调用方法
		// 输出结果
		for (Set<Integer> subSet : result) {
			for (Integer num : subSet)
				System.out.print(num);

			System.out.println("");
		}
	}

	public static Set<Set<Integer>> getSubSet(int[] set) {
		Set<Set<Integer>> result = new HashSet<Set<Integer>>(); // 用来存放子集的集合,如{{},{1},{2},{1,2}}
		int length = set.length;
		int num = length == 0 ? 0 : 1 << (length); // 2的n次方,若集合set为空,num为0;若集合set有4个元素,那么num为16.

		// 从0到2^n-1([00...00]到[11...11])
		for (int i = 0; i < num; i++) {
			Set<Integer> subSet = new HashSet<Integer>();
			int index = i;
			for (int j = 0; j < length; j++) {
				if ((index & 1) == 1) { // 每次判断index最低位是否为1,为1则把集合set的第j个元素放到子集中
					subSet.add(set[j]);
				}
				index >>= 1; // 右移一位
			}

			result.add(subSet); // 把子集存储起来
		}
		return result;
	}

}

结果:


1
2
12
3
13
23
123

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部