文档章节

返回某集合的所有子集

一贱书生
 一贱书生
发布于 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
Scala之集合上常见的函数式风格的操作汇总

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

bluishglc
2016/11/24
0
0
List/Set/Map集合排序/有序集合

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

秋风醉了
2014/09/11
0
0
列出所有的子集

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

SVD
2016/03/03
39
0

没有更多内容

加载失败,请刷新页面

加载更多

Ubuntu18.04 安装MySQL

1.安装MySQL sudo apt-get install mysql-server 2.配置MySQL sudo mysql_secure_installation 3.设置MySQL非root用户 设置原因:配置过程为系统root权限,在构建MySQL连接时出现错误:ERROR...

AI_SKI
今天
2
0
3.6 rc脚本(start方法) 3.7 rc脚本(stop和status方法) 3.8 rc脚本(以daemon方式启动)

3.6-3.7 rc脚本(start、stop和status方法) #!/usr/bin/env python# -*- coding: utf-8 -*-# [@Version](https://my.oschina.net/u/931210) : python 2.7# [@Time](https://my.oschina.......

隐匿的蚂蚁
今天
3
0
Cnn学习相关博客

CNN卷积神经网络原理讲解+图片识别应用(附源码) 笨方法学习CNN图像识别系列 深度学习图像识别项目(中):Keras和卷积神经网络(CNN) 卷积神经网络模型部署到移动设备 使用CNN神经网络进行...

-九天-
昨天
4
0
flutter 底部输入框 聊天输入框 Flexible

想在页面底部放个输入框,结果键盘一直遮住了,原来是布局问题 Widget build(BuildContext context) { return Scaffold( appBar: AppBar( title: Text("评论"), ...

大灰狼wow
昨天
4
0
Kernel I2C子系统

备注:所有图片来源于网络 1,I2C协议: 物理拓扑: I2C总线由两根信号线组成,一条是时钟信号线SCL,一条是数据信号线SDA。一条I2C总线可以接多个设备,每个设备都接入I2C总线的SCL和SDA。I...

yepanl
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部