采用
位掩码实现打印给定数组所有的非空子集。
分析:
首先来看一个例子,如果给定一个正整数N,如何输出由1到N组成的数组所有的非空子集呢?
如N=3, 那么1到3组成的数组为{1,2,3},数组长度为3,那么二进制表示有
1<<3 = 8种。
0 = 000 = {} 空集
1 = 001 = {1}
2 = 010 = {2}
3 = 011 = {1, 2}
4 = 100 = {3}
5 = 101 = {1, 3}
6 = 110 = {2, 3}
7 = 111 = {1, 2, 3}
遍历所有的二进制表达式,考虑其中1的位置,并打印相应的值,就能得到我们想要的结果。
代码如下:
/**
*
* 给定一个正整数N,输出由1到N组成的数组所有的非空子集。
* 如N=3, 那么1到3组成的数组为{1,2,3}
*
* 所有二进制的情况
*
* 0 = 000 = {} 空集
* 1 = 001 = {1}
* 2 = 010 = {2}
* 3 = 011 = {1, 2}
* 4 = 100 = {3}
* 5 = 101 = {1, 3}
* 6 = 110 = {2, 3}
* 7 = 111 = {1, 2, 3}
*
*/
public void printAllSubsets(int N) {
if (N <=0) {
throw new IllegalArgumentException("参数应该是一个正整数。");
}
int allMasks = 1 << N;
//如考虑空集 ,那么i的初始值为0
for (int i = 1; i < allMasks; i++) {
for (int j = 0; j < N; j++)
if ((i & (1 << j)) > 0)
System.out.print((j + 1) + " ");
System.out.println();
}
}
依据上述例子的实现方式,下面的方法实现打印一个字符串数组所拥有的所有非空子集。
/**
* 打印一个数组所有的非空子集
*/
public void printAllSubsets(String[] array) {
if (null == array || 0 == array.length) {
throw new IllegalArgumentException("数组不能为Null,至少有一个元素");
}
// 数组长度
int len = array.length;
// 根据数据的长度,得出所有二进制的个数
// 如len =2;
// 0 = 00 = {}
// 1 = 01 = {1}
// 2 = 10 = {2}
// 3 = 11 = {1, 2}
int allMasks = 1 << len;
// 遍历所有的二进制表示方式
for (int i = 1; i < allMasks; i++) {
for (int j = 0; j < len; j++)
if ((i & (1 << j)) > 0)
System.out.print(array[j] + " ");
System.out.println();
}
}
具体的代码和简单的测试如下:
public class PrintAllNonEmptySubsets {
/**
*
* 给定一个正整数N,输出由1到N组成的数组所有的非空子集。
* 如N=3, 那么1到3组成的数组为{1,2,3}
*
* 所有二进制的情况
*
* 0 = 000 = {} 空集
* 1 = 001 = {1}
* 2 = 010 = {2}
* 3 = 011 = {1, 2}
* 4 = 100 = {3}
* 5 = 101 = {1, 3}
* 6 = 110 = {2, 3}
* 7 = 111 = {1, 2, 3}
*
*/
public void printAllSubsets(int N) {
if (N <=0) {
throw new IllegalArgumentException("参数应该是一个正整数。");
}
int allMasks = 1 << N;
//如考虑空集 ,那么i的初始值为0
for (int i = 1; i < allMasks; i++) {
for (int j = 0; j < N; j++)
if ((i & (1 << j)) > 0)
System.out.print((j + 1) + " ");
System.out.println();
}
}
/**
* 打印一个数组所有的非空子集
*/
public void printAllSubsets(String[] array) {
if (null == array || 0 == array.length) {
throw new IllegalArgumentException("数组不能为Null,至少有一个元素");
}
// 数组长度
int len = array.length;
// 根据数据的长度,得出所有二进制的个数
// 如len =2;
// 0 = 00 = {}
// 1 = 01 = {1}
// 2 = 10 = {2}
// 3 = 11 = {1, 2}
int allMasks = 1 << len;
// 遍历所有的二进制表示方式
for (int i = 1; i < allMasks; i++) {
for (int j = 0; j < len; j++)
if ((i & (1 << j)) > 0)
System.out.print(array[j] + " ");
System.out.println();
}
}
public static void main(String[] args) {
PrintAllNonEmptySubsets exam = new PrintAllNonEmptySubsets();
exam.printAllSubsets(new String[] { "a", "b", "c" });
exam.printAllSubsets(3);
}
}
输出结果:
a
b
a b
c
a c
b c
a b c
1
2
1 2
3
1 3
2 3
1 2 3
分享到:
相关推荐
N个元素的集合{1,2,3...,n}可以划分为若干个非空子集。例如,当n=2时,集合{1,2,3}可以划分为2个不同的非空子集如下:{{1},{2}},{{1,2}}。编程任务:给定正整数N,计算出N个元素的集合{1,2,3,.....n}可以划分为...
js中获取只包含一种字符的最长非空子字符串的长度
集合划分:包含n个元素的集合划分为正好k个非空子集的方法的数目
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7 个。 注意在计算时,只算本质不同的串的个数。 请问,字符串...
本文得到以下的结论:1.在G是有限群时,A是G的某一子群的商群。2.在G是无限群时,我们构造出A不是G的任何子群的商群的例子。3.A是G的商群的充要条件是:
1. 问题描述:n个元素的集合{1,2,..., n }可以划分为若干个非空子集。例如,当n = 4 时,集合{1,2,3,4}可以划分为15 个不同的非空子...每组有且仅有一行为一个正整数n( 0 )。 输出:输出n个元素集合的非空子集数。
将所有人工鱼集合也对应划分为若干个非空子集。在人工鱼的觅食、聚群和追尾过程中,人工鱼从一个位置状态转移到任意一个位置状态的转移概率可以计算出来;人工鱼移动过程中的每个位置状态对应于有限Markov链上的一个...
一组 n 个元素可以划分为非空子集。 这个包提供了列出所有可能的分区的功能。 分区数为贝尔数。 可以选择指定组成分区的子集的数量。 分区数是第二类斯特林数。
如果对列不为空,则获取并打印队列头,然后将队列头的左右非空子节点放入队列。重复该操作即可。 以下为具体解答: public ArrayList PrintFromTopToBottom(TreeNode root) { if (root == null) { return new ...
Apriori算法是挖掘布尔关联规则频繁项集的算法 ...Apriori算法是反单调的,即一个集合如果不能通过测试,则该集合的所有超集也不能通过相同的测试。 Apriori性质通过减少搜索空间,来提高频繁项集逐层产生的效率
Apriori性质:频繁项集的所有非空子集都必须也是频繁的。(一种反单调性质) 算法描述: 1、链接步:通过L自连接产生候选k项集C。 2、剪枝步:C是L的超集。利用Apriori性质,如果一个k项集的(k-1)项集不在L中,则该...
leetcode切割分组 The algorithms implemented in Java Project Description ...给定一个由字符串组成的数组,必须把所有的字符串拼接起来, 返回所有可能的拼接结果中,字典序最小的结果 04/13 第14课 会议
首先从氨基酸的同义密码子角度定义了一个反映两序列间同源性的公式,然后建立矩阵并在矩阵上定义运算来检测S的任一非空子集与T的任一非空子集的同源性,命名这种方法为矩阵法,在此基础上进行逐步搜索。通过选取...
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实: 算法使用频繁项 集性质的先验知识。Apriori使用一种称作逐层搜索的...Apriori性质: 频繁项集的所有非空子集都必须也是频繁的。
概率论与数理统计答案 第三版 浙江大学 盛骤 谢式千
第十届蓝桥杯Java大学本科B组省赛试题
1、将大的网络划分为小的网络,目的是控制广播 ...例题1:单位申请到138.138.0.0的网络,需要6个机房,求: 138.138.0.0 6=(110)2 255.255.0.0 向主机借 3位用于子网 255.255.11100000.00000000 255.255.224.0
一个字符串的非空子串是指字符串中长度至少为1 的连续的一段字符组成的串。例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7个。 注意在计算时,只算本质不同的串的个数。 请问,字符串...
基于空子载波的OFDMA上行链路载频偏迭代盲估计方法,张渭乐,殷勤业,本文提出一种基于空子载波的OFDMA上行链路载频偏迭代盲估计方法,适用于以子载波片为最小分配单位的任意分配方案。在上行链路传输�
n 个元素的集合{1,2,., n }可以划分为若干个非空子集。给定正整数n 和m,计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。