文档章节

返回某集合的所有子集

一贱书生
 一贱书生
发布于 2016/11/22 10:19
字数 517
阅读 4
收藏 0
点赞 0
评论 0

/**

 * 功能:返回某集合的所有子集。

 */

 

三种方法:

方法一:迭代

[java] view plain copy

 

  1. //迭代  
  2. /** 
  3.  * 注意:每次加入集合后会改变原来的集合,无法继续从集合中取出元素。 
  4.  *      必须通过一个中间参数moreSubsets来保存中间结果,最后加入allSubsets。 
  5.  * @author Lynne 
  6.  * @param set 
  7.  * @param index 
  8.  * @return 
  9.  */  
  10. public static ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set,int index){  
  11.     ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();  
  12.       
  13.     allSubsets.add(new ArrayList<Integer> ());//加入空集合  
  14.       
  15.     while(index<set.size()){  
  16.         int item=set.get(index);  
  17.         ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>();    
  18.           
  19.         for(ArrayList<Integer> subsets:allSubsets){  
  20.             ArrayList<Integer> newSubsets=new ArrayList<Integer>();  
  21.             newSubsets.addAll(subsets);  
  22.             newSubsets.add(item);  
  23.             moreSubsets.add(newSubsets);  
  24.         }  
  25.         allSubsets.addAll(moreSubsets);  
  26.         index++;  
  27.     }  
  28.     return allSubsets;  
  29. }  

 

方法二:递归

[java] view plain copy

 

  1. //递归法  
  2. /** 
  3.  * 思路:简单构造法 
  4.  *      计算P(n-1),复制一份结果,然后在每个复制后的集合中加入an。 
  5.  * @param set 
  6.  * @param index 
  7.  * @return 
  8.  */  
  9. public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set,int index){  
  10.     ArrayList<ArrayList<Integer>> allSubsets;  
  11.       
  12.     if(set.size()==index){//终止条件,加入空集合  
  13.         allSubsets=new ArrayList<ArrayList<Integer>>();  
  14.         allSubsets.add(new ArrayList<Integer>());//空集合  
  15.     }else{  
  16.         allSubsets=getSubsets(set, index+1);  
  17.         int item=set.get(index);  
  18.         ArrayList<ArrayList<Integer>> moreSubsets=new ArrayList<ArrayList<Integer>>();    
  19.           
  20.         for(ArrayList<Integer> subsets:allSubsets){  
  21.             ArrayList<Integer> newSubsets=new ArrayList<Integer>();  
  22.             newSubsets.addAll(subsets);  
  23.             newSubsets.add(item);  
  24.             moreSubsets.add(newSubsets);  
  25.         }  
  26.         allSubsets.addAll(moreSubsets);  
  27.     }         
  28.     return allSubsets;  
  29. }  

 

方法三:组合数学

[java] view plain copy

 

  1. //组合数学  
  2. /** 
  3.  * 思路:迭代访问1到2^n的所有数字,再转化为集合 
  4.  * 每个元素有两个选择:1)在集合中(“yes”);2)不在集合中(“no”)。即每个子集都是一串yes和no。 
  5.  * 总共有2^n个子集,将每个yes看做1,每个no看做0,即可以表示为一个二进制串。 
  6.  * 所以,构造所有的子集就等同于构造所有的二进制数。迭代访问1到2^n的所有数字,再转化为集合。 
  7.  * @param set 
  8.  * @return 
  9.  */  
  10. public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set){  
  11.     ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();  
  12.       
  13.     int size=1<<set.size();//集合的子集个数,计算2^n。  
  14.     for(int i=0;i<size;i++){  
  15.         ArrayList<Integer> subsets=new ArrayList<Integer>();  
  16.         subsets=convertIntToSet(i);  
  17.         allSubsets.add(subsets);  
  18.     }  
  19.       
  20.     return allSubsets;  
  21. }  
  22.   
  23. public static ArrayList<Integer> convertIntToSet(int x){  
  24.     ArrayList<Integer> subsets=new ArrayList<Integer>();  
  25.     for(int i=x;i>=1;i>>=1){  
  26.         if((i&1)==1)  
  27.             subsets.add(i);  
  28.     }         
  29.     return subsets;  
  30. }  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
python--集合set类型

* 集合set类型 *** 集合的定义 set = {} set = {1,2,3} set = {1,2,3,1,2,3} set = {1,2,3,'hello'} set = {1,2,3,'hello',(1,2,3)} 集合不重复: 列表转化为: 示例: set的应用场景 集合是...

cuijb0221 ⋅ 2017/07/14 ⋅ 0

python核心编程笔记chapter 7

字典 映射类型的建直接或间接地和储存的数据相关联。无序的数据集。有序keys()、values()、无序items() dict()方法、adict = ((['x', 1],['y', 2])) fromkeys方法: adict = {}.from...

MRFung ⋅ 2015/12/28 ⋅ 0

List/Set/Map集合排序/有序集合

其中 Set代表无序、不可重复的集合; List代表有序、重复的集合; Map则代表具有映射关系的集合。 Queue体系集合代表一种队列集合实现。 使用Collections.sort对List集合排序 Collections.so...

秋风醉了 ⋅ 2014/09/11 ⋅ 0

Scala之集合上常见的函数式风格的操作汇总

目录 正文 函数式编程对集合操作有一些通行的“叫法”,或者更像是一些“俚语”,它们的含义清晰明确,但是很难顾名思义,比如常见的“filter”,”map”,”flatMap”,“redue”等等。本文会...

bluishglc ⋅ 2016/11/24 ⋅ 0

NSSet 集合对象

集合 NSSet 对象是一组单值对象的组合,比如,1个包含1到50的数字的集合。集合对象的操作包括搜索、添加、删除集合中的成员(可变集合的功能),比较两个集合,计算两个集合的交集和并集等。...

晨曦之光 ⋅ 2012/03/12 ⋅ 0

学习 TLA+ - 基础数学知识

TLA+ 并不是一门很容易掌握的语言,在学习之前,我们需要了解一些简单的数学知识。这里需要注意,为了打字方便,很多数学符号我直接使用了 ASCII 来表示,具体符号与 ASCII 的对应,大家可以...

siddontang ⋅ 2017/11/19 ⋅ 0

列出所有的子集

算法要求 编写一个程序,列出{1,2,3,…,n}这个集合的所有子集,包括空集合。 列出一个集合的所有子集有很多做法,题目中并没有要求依某个特定的次序来排列, 因此是不难做出来的。 因为集...

SVD ⋅ 2016/03/03 ⋅ 0

第十章 Scala 容器基础(十九):把序列分解成子集(group by,partition等)

Problem 你想要基于一种算法或者规则,把一个序列切分为两个或者多个子集。 Solution 使用groupBy,partition,span,splitAt方法可以把一个集合切分成子集合。sliding和unzip方法也可以用来...

阿拉德大陆的魔法师 ⋅ 2016/04/14 ⋅ 0

集合的整数表示

有一类问题是需要表示包含N个索引数字集合S = {0,1,...,n-1}的某个子集,这种子集(假设有k个元素,k<=n)可以用一个整数表示: SK = 2^a1 + 2^a2 +...+ 2^ak subs={a1,a2,...,ak} SK是subs的整...

三川_8f54 ⋅ 2017/10/28 ⋅ 0

3、Java基础复习----集合 Collection、List

1.容器 Java 所提供的一系列类的实例,用于在程序中存放对象 java.util Collection Interface List interface (有序可重复) Set interface(无序不可重复) public boolean add(E e);添加一个对...

baibuxiha ⋅ 2016/01/20 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python爬虫,抓取淘宝商品评论内容

作为一个资深吃货,网购各种零食是很频繁的,但是能否在浩瀚的商品库中找到合适的东西,就只能参考评论了!今天给大家分享用python做个抓取淘宝商品评论的小爬虫! 思路 我们就拿“德州扒鸡”...

python玩家 ⋅ 18分钟前 ⋅ 0

MySQL 内核深度优化

MYSQL数据库适用场景广泛,相较于Oracle、DB2性价比更高,Web网站、日志系统、数据仓库等场景都有MYSQL用武之地,但是也存在对于事务性支持不太好(MySQL 5.5版本开始默认引擎才是InnoDB事务...

java高级架构牛人 ⋅ 40分钟前 ⋅ 0

用户登录信息-钉子效果(基于jquery2.0)

本js效果使用jquery2.0,清晰的分解用户登录信息的(钉子效果),该效果直接用在作者网站(www.phpkhbd.com)上。 里面的难点有:定时器,延时。 大致效果如下: 一开始: 鼠标放上去的时候:...

宁哥实战课堂 ⋅ 42分钟前 ⋅ 0

解决yum安装报错Protected multilib versions

使用yum安装报错Protected multilib versions原因是因为多个库不能共存,不过更新的话也并不行,但是可以在安装命令后面加上如下一段命令: --setopt=protected_multilib=false 案例: 比如需...

北岩 ⋅ 53分钟前 ⋅ 0

为什么要学习Typescript???

简单来说 目前的typescript就是未来的javascript 为什么?? 这要从ECMA-262标准的第4版说起 对了 我们说的ES5 其实是ECMAScript3.1这个替代性建议被扶正了而已... 那么 第4版标准是什么? 看看...

hang1989 ⋅ 57分钟前 ⋅ 0

linux安装ipfs

一、下载ipfs # cd /usr/local/ipfs/ # wget https://dist.ipfs.io/go-ipfs/v0.4.15/go-ipfs_v0.4.15_linux-amd64.tar.gz # tar -zxvf go-ipfs_v0.4.15_linux-amd64.tar.gz 二、安装ipfs # ......

八戒八戒八戒 ⋅ 今天 ⋅ 0

jvm程序执行慢诊断手册

生产环境最多的几种事故之一就是程序执行慢,如果是web服务的话,表现就是响应时间长。本文分享,从业多年形成的排查守则。 诊断步骤 系统资源查看 首先是系统资源查看,而且必须是在第一步。...

xpbob ⋅ 今天 ⋅ 0

YII2 advanced 高级版本项目搭建-添加API应用以及多应用

一、YII安裝 安裝yii可以用composer安裝,也可以在yii中文社区下载归档文件安装 composer安装就不介绍了,因为要安装composer,比较麻烦,当然安装了composer是最好的,以后安装yii的插件要用...

botkenni ⋅ 今天 ⋅ 0

在jdk1.8的环境下模拟永久代内存溢出

相信不少小伙伴在看深入理解Java虚拟机的时候,作者给我们举例一个demo来发生PermGen space 1、通过List不断添加String.intern(); 2、通过设置对应的-XX:PermSize与-XX:MaxPermSize(更快看到...

虾几把写 ⋅ 今天 ⋅ 0

开发OpenDaylight组件的完整流程

在前面介绍学习了OpenDaylight的几个重要模块后,这里再来介绍下完整开发一个模块的过程。 OSGI的bundles提供被其他OSGI组件调用的服务。这个教程中展示的是Data Packet Service去解析数据包...

wangxuwei ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部