文档章节

返回某集合的所有子集

一贱书生
 一贱书生
发布于 2016/11/22 10:19
字数 517
阅读 4
收藏 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
博文 724
码字总数 600123
作品 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
0
python核心编程笔记chapter 7

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

MRFung
2015/12/28
16
0
List/Set/Map集合排序/有序集合

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

秋风醉了
2014/09/11
0
0
Scala之集合上常见的函数式风格的操作汇总

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

bluishglc
2016/11/24
0
0
学习 TLA+ - 基础数学知识

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

siddontang
2017/11/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

初级开发-编程题

` public static void main(String[] args) { System.out.println(changeStrToUpperCase("user_name_abc")); System.out.println(changeStrToLowerCase(changeStrToUpperCase("user_name_abc......

小池仔
今天
4
0
现场看路演了!

HiBlock
昨天
14
0
Rabbit MQ基本概念介绍

RabbitMQ介绍 • RabbitMQ是一个消息中间件,是一个很好用的消息队列框架。 • ConnectionFactory、Connection、Channel都是RabbitMQ对外提供的API中最基本的对象。Connection是RabbitMQ的s...

寰宇01
昨天
9
0
官方精简版Windows10:微软自己都看不过去了

微软宣布,该公司正在寻求解决方案,以减轻企业客户的Windows 10规模。该公司声称,企业客户下载整个Windows 10文件以更新设备既费钱又费时。 微软宣布,该公司正在寻求解决方案,以减轻企业...

linux-tao
昨天
19
0
TypeScript基础入门之JSX(二)

转发 TypeScript基础入门之JSX(二) 属性类型检查 键入检查属性的第一步是确定元素属性类型。 内在元素和基于价值的元素之间略有不同。 对于内部元素,它是JSX.IntrinsicElements上的属性类型...

durban
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部