文档章节

返回某集合的所有子集

一贱书生
 一贱书生
发布于 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

idea新建springCloud项目(5)- 订单服务

1.创建订单api,如下: 2.创建订单实现逻辑 3.新建订单、订单商品表 -- 订单 create table `order_master` ( `order_id` varchar(32) not null, `buyer_name` varchar(32) not null comment......

monroeCode
18分钟前
1
1
游戏开发经验谈(二):对战类全球服游戏的设计与实现

上篇文章《游戏开发经验谈(一):游戏架构里隐藏的五个坑及其应对方案》,我们主要讲解了游戏架构设计当中隐藏的一些坑及其应对方案,错过的小伙伴可以回溯之前的内容。本期内容,将会重点介...

UCloudTech
28分钟前
0
0
Mysql基本语法

一.联合主键 drop table CONTENT_AND_CATALOG;CREATE TABLE `tobebetter`.`CONTENT_AND_CATALOG` ( `ID` VARCHAR(120) NOT NULL , `CONTENT_ID` VARCHAR(120) , `CA......

我是菜鸟我骄傲
29分钟前
0
0
179. centos7 安装mariadb

1. centos7 中安装mariadb 1.1 执行安装 centos7 自带了mariadb yum -y install mariadb mariadb-server 1.2 启动mariadb systemctl start mariadb 1.3 设置开机启动 systemctl enable maria......

Lucky_Me
36分钟前
0
0
【AI实战】动手训练自己的目标检测模型(YOLO篇)

在前面的文章中,已经介绍了基于SSD使用自己的数据训练目标检测模型(见文章:手把手教你训练自己的目标检测模型),本文将基于另一个目标检测模型YOLO,介绍如何使用自己的数据进行训练。 ...

雪饼
42分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部