文档章节

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

孟飞阳
 孟飞阳
发布于 2016/06/15 16:08
字数 465
阅读 809
收藏 0

思路:

        假设集合有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

 

© 著作权归作者所有

孟飞阳
粉丝 217
博文 1056
码字总数 566359
作品 5
朝阳
个人站长
私信 提问
Java核心(四)你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧! Java中的集合通常指的是Collection下的三个集合框架List、Set、Q...

王磊的博客
2018/11/28
108
0
Java 新特性,使用 Lambdas 表达式作为 Predicates

以前我给过一个例子,查询地图的参数变成了 SOLR 的搜索字符串。在 Java 8 之前的代码使用传统的for循环条件和使用StringBuilder 逐步构建一个字符串。Java 8 代码使用 map 实体,映射(转换...

oschina
2016/09/21
3.3K
8
Effective Java 第三版——47. 优先使用Collection而不是Stream来作为方法的返回类型

Tips 《Effective Java, Third Edition》一书英文版已经出版,这本书的第二版想必很多人都读过,号称Java四大名著之一,不过第二版2009年出版,到现在已经将近8年的时间,但随着Java 6,7,8...

M104
2018/09/30
0
0
Java NIO之Selector(选择器)

历史回顾: Java NIO 概览 Java NIO 之 Buffer(缓冲区) Java NIO 之 Channel(通道) 其他高赞文章: 面试中关于Redis的问题看这篇就够了 一文轻松搞懂redis集群原理及搭建与使用 超详细的Jav...

山川_84b6
2018/05/16
0
0
从 Java 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
764
3

没有更多内容

加载失败,请刷新页面

加载更多

STM32进阶之串口环形缓冲区实现

队列的概念 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 队列...

杰杰1号
15分钟前
4
0
设计模式-建造者模式

建造者模式 定义 将一个复杂对象的构建和它的表示分离,使得同样的构建过程创建出不同的表示。这句话理解起来优点抽象,我们打个简单的比方吧,中国人都喜欢做菜,做菜的时候后会放很多配料...

木本本
18分钟前
4
0
017、xml版本代码生成器配置

1、在pom.xml文件中增加mybatis-generator-maven-plugin插件 <build> <plugins> <plugin> <groupId>org.mybatis.generator</groupId> <artifactId>......

北岩
30分钟前
3
0
用jQuery-Easy-UI编写注册页面

本文转载于:专业的前端网站➮用jQuery-Easy-UI编写注册页面 1 <!DOCTYPE html> 2 <html lang="en"> 3 4 <head> 5 <meta charset="UTF-8"> 6 <meta name="viewport" content=......

前端老手
38分钟前
2
0
Git ssh配置

生成密钥对 ssh-keygen -t rsa -C "email@email.com"邮箱替换自己邮箱在地址C:\Users\账户\.ssh下,id_rsa、id_rsa.pub两个文件复制文件id_rsa.pub内容到github\gitlab的Settings-> SSH ......

JUKE
46分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部