题目:给定一个集合,求该集合的所有子集合,如集合{1,2}的子集合有{}(空集是所有集合的子集),{1},{2},{1,2},共2^2个子集合,下面给出两种解法,其中第一种解法分递归与非递归实现,都用java实现。
【第一种解法】
算法思想:给定一个集合,求子集合过程可分为以下两个步骤:
(1)把集合分为两部分,第一个元素和剩余元素,如{1,2,3}分为1和{2,3}
(2)原集合的所有子集合为剩余元素的子集合并上把第一个元素加入所有子集合,如{2,3}的子集合为{2},{3},{2,3},{},那么把第一个元素1加入这些子集合,则构成{1,2},{1,3},{1,2,3},{1},把这些集合合并起来,则原集合的所有子集合便为{2},{3},{2,3},{},{1,2},{1,3},{1,2,3},{1},代码如下:
【非递归实现】
package bitSet; import java.util.ArrayList; public class SubSet { public static void main(String[] args) { int array[] = { 1, 2, 3, 4, 5, 6 }; ArrayList<ArrayList<Integer>> allSet = new ArrayList<ArrayList<Integer>>(); allSet.add(new ArrayList<Integer>()); for (int i = 0; i < array.length; i++) { ArrayList<ArrayList<Integer>> subSet = new ArrayList<ArrayList<Integer>>(); for (int j = 0; j < allSet.size(); j++) { ArrayList<Integer> element = new ArrayList<Integer>(); element.add(array[i]); element.addAll(allSet.get(j)); subSet.add(element); } allSet.addAll(subSet); } int count = 0; for (int i = 0; i < allSet.size(); i++) { ArrayList el = allSet.get(i); for (int j = 0; j < el.size(); j++) { System.out.print(el.get(j) + " "); } count++; System.out.println(); } System.out.println(count); } }
【递归实现】
package bitSet; import java.util.ArrayList; public class SubSet1 { static ArrayList<ArrayList<Integer>> getSubsets(int[] set, int index) { ArrayList<ArrayList<Integer>> allsubsets; if (set.length == index) { allsubsets = new ArrayList<ArrayList<Integer>>(); allsubsets.add(new ArrayList<Integer>()); // Empty set } else { allsubsets = getSubsets(set, index + 1); int item = set[index]; ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>(); for (ArrayList<Integer> subset : allsubsets) { ArrayList<Integer> newsubset = new ArrayList<Integer>(); newsubset.addAll(subset); // newsubset.add(item); moresubsets.add(newsubset); } allsubsets.addAll(moresubsets); } return allsubsets; } public static void main(String[] args) { int array[] = { 1, 2, 3, 4, 5, 6 }; ArrayList<ArrayList<Integer>> allSet = getSubsets(array,0); int count = 0; for (int i = 0; i < allSet.size(); i++) { ArrayList el = allSet.get(i); for (int j = 0; j < el.size(); j++) { System.out.print(el.get(j) + " "); } count++; System.out.println(); } System.out.println(count); } }
【第二种解法】
算法思想:n个元素的集合,在构造子集合过程中,每个元素有两种情况,在子集合中“存在”与“不存在”,“存在”用“1”表示,“不存在”用“0”表示,这样共有2^n种情况,即2^n个子集合。此时我们想到用长度为n的二进制数字 “1111....000...”,1表示该位置在子集合中存在,0表示该位置在子集合中不存在,让该二进制数从0 一直加到 2^n,则所有情况都会出现,代码如下
package bitSet; import java.util.ArrayList; public class SubSet3 { static ArrayList<ArrayList<Integer>> getSubsets(int[] set) { ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>(); int max = 1 << set.length; for (int i = 0; i < max; i++) { ArrayList<Integer> subset = new ArrayList<Integer>(); int k = i; int index = 0; while (k > 0) { if ((k & 1) > 0) { subset.add(set[index]); } k >>= 1; index++; } allsubsets.add(subset); } return allsubsets; } public static void main(String[] args) { int array[] = { 1, 2, 3, 4, 5, 6 }; ArrayList<ArrayList<Integer>> allSet = getSubsets(array); int count = 0; for (int i = 0; i < allSet.size(); i++) { ArrayList el = allSet.get(i); for (int j = 0; j < el.size(); j++) { System.out.print(el.get(j) + " "); } count++; System.out.println(); } System.out.println(count); } }
相关推荐
求子集c++算法
C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据结构算法集合 C++ 数据...
基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust 算法集合2024基于Rust ...
JAVA 经典算法集合(1),JAVA 经典算法集合(1),JAVA 经典算法集合(1),JAVA 经典算法集合(1),JAVA 经典算法集合(1),JAVA 经典算法集合(1),JAVA 经典算法集合(1)JAVA 经典算法集合(1),JAVA 经典...
数据结构书上的KMP算法,书上的算法看的不太明白,自己写了一个,有点罗嗦。 也是自己写的,容易看懂
Java数据挖掘18大算法实现和10大常见排序算法以及其他相关经典DM算法集合。 18大数据挖掘的经典算法以及代码实现,涉及到了决策分类,聚类,链接挖掘,关联挖掘,模式挖掘等等方面,后面都是相应算法的文章,希望能够...
包括模拟退火、汉密尔顿回路、随机数、网络流、规划、解方程、数据分析等的经典算法
一个程序,很好的。是关于如何用回溯法求子集和的。
人工智能计算算法集合项目源代码。包含:蚁群算法、粒子群算法、BP神经网络、高斯概率模型的分布估计算法、遗传算法、BP神经网络、贪婪算法。 人工智能计算算法集合项目源代码。包含:蚁群算法、粒子群算法、BP神经...
JAVA 经典算法书集合(2),JAVA 经典算法书集合(2),JAVA 经典算法书集合(2),JAVA 经典算法书集合(2),JAVA 经典算法书集合(2),JAVA 经典算法书集合(2),JAVA 经典算法书集合(2)JAVA 经典算法书集合...
代码 100多种数据处理与分类算法集合代码 100多种数据处理与分类算法集合代码 100多种数据处理与分类算法集合代码 100多种数据处理与分类算法集合代码 100多种数据处理与分类算法集合代码 100多种数据处理与分类算法...
100多种数据处理与分类算法集合(Matlab实现)
C语言实现的各种算法,排序 哈希 查找 栈 队列等等~~~
用于教育目的,C# 实现的各种算法的集合。存储库是用 C# 实现的各种算法的集合。这些算法涵盖各种主题 从计算机科学、数学和统计学、数据科学、机器学习、工程学等。实现 及其相关文档旨在为教育工作者和学生提供...
这份代码用 C++ 的模板类实现了一个集合类 Set,其 API 参考借鉴了 STL 中的 vector 类,采用动态内存及链表进行元素管理,并实现了一些常见的集合算法:并集、交集,也实现了随机下标的存取。
一个优秀的算法集合构造,算法从这儿开始一个优秀的算法集合构造
算法大集合.chm 算法大集合.chm算法大集合.chm
对于一些经典算法介绍的集合
数据结构算法C语言代码实现集合 链表、单链表、双链表、循环链表、二叉树、二分查找、顺序表、队列、栈、图等各种算法的C语言代码实现 我遇到的最好的算法实现了,多亏了它!
这是在算法分析与复杂性课程里面,利用概率算法判定两个集合是否会相等的代码