文档章节

返回某集合的所有子集

一贱书生
 一贱书生
发布于 2016/11/22 10:19
字数 517
阅读 74
收藏 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. }  

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中

评论(0)

JavaScript数据结构——集合的实现与应用

  与数学中的集合概念类似,集合由一组无序的元素组成,且集合中的每个元素都是唯一存在的。可以回顾一下中学数学中集合的概念,我们这里所要定义的集合也具有空集(即集合的内容为空)、交...

Jaxu
2019/08/02
0
0
【 数据集合】并集、交集、差集、子集

什么是集合? 集合是由一组无序且唯一的项组成。你可以把集合想象成一个既没有重复元素,也没有顺序概念的数组。还有一个概念叫空集。空集就是不包括任何元素的集合。空集用{}表示。 创建集合...

前端旺仔
2019/06/26
0
0
JavaScript实现集合与字典

JavaScript实现集合与字典 一、集合结构 1.1.简介 集合比较常见的实现方式是哈希表,这里使用JavaScript的Object类进行封装。 集合通常是由一组无序的、不能重复的元素构成。 数学中常指的集...

osc_gh68xcjy
03/12
1
0
odoo10学习笔记九:Odoo10 API

转载请转载原文地址:https://www.cnblogs.com/ygj0930/p/11189315.html 一:纪录集API model中的数据是以集合的形式使用的,因此可以使用集合运算来操作。 集合运算符 record in set返回rec...

.长卿
2019/07/15
0
0
每周一练 之 数据结构与算法(Set)

这是第四周的练习题,五一放假结束,该收拾好状态啦。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据结构与算法(LinkedList) 3.每周一练 之 数据结构...

pingan8787
2019/05/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

腾讯副总裁魏颖:提瓢入市,倚杖而归

  魏颖,腾讯公司副总裁,2008 年加入腾讯,全面负责公司薪酬福利、绩效管理、员工关系以及海外业务人力资源。   ————————   很多人对人力资源(HR)工作的理解就是一些人事流...

alkcendkljk
今天
13
0
OSChina 周二乱弹 —— 我要一份儿大姐姐的爱

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @Cobbage :分享赵雷的单曲《阿刁 (Diao)》: 《阿刁 (Diao)》- 赵雷 手机党少年们想听歌,请使劲儿戳(这里) @喵星人123 :昨天睡到半夜 突然...

小小编辑
今天
11
0
window下 mongodb开启用户名和密码 权限

在默认情况下,mongod是监听在127.0.0.1之上的,任何客户端都可以直接连接27017,且没有认证。 好处是,用户可以即时上手,不用担心被一堆配置弄的心烦意乱。 坏处是,公网服务器搭建MongoDB...

东东笔记
今天
9
0
数据倾斜

数据倾斜: 两种数据倾斜发生的现象: 80%情况下都发生挂了,只有极少20%情况下能把task执行完成 窄依赖:结构简单,如果发生数据丢失,方便查找丢失的数据 宽依赖:结构复杂,如何发生数据丢...

七宝1
今天
20
0
我的jdk源码(十一):ArrayList

一、概述 ArrayList类是AbstractList的子类,实现了具体的add(), set(), remove()等方法。它是一个可调整大小的数组可以用来存放各种形式的数据。 二、源码分析 (1) 类的声明,源码如下: ...

Java觉浅
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部