的功率集 {1, 2, 3}
是: {{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
假设我有一个 Set
在java中:
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
如何以最佳的复杂度顺序编写getpowerset函数(我想可能是o(2^n)
26条答案
按热度按时间li9yvcax16#
jvlzgdj917#
i2loujxw18#
这里是发电机组。想法是第一个=
S[0]
小的一套也可以S[1,...n]
.计算smallerset的所有子集并将它们放入allsubset中。
对于allsubsets中的每个子集,克隆它并首先将其添加到子集中。
bqujaahr19#
另一个解决方案是使用java8+流式api,它是惰性的,并且是有序的,所以当它与“limit()”一起使用时,它返回正确的子集。
客户端代码是
/打印:【】[a][b][c][d][e][a,b][a,c][b,c]/
2jcobegt20#
如果s是有n个元素的有限集,则s的幂集包含2^n个元素。简单枚举powerset元素的时间是2^n,所以
O(2^N)
是构造幂集的时间复杂度的下界。简单地说,任何涉及到创建功率集的计算都不会扩展到n的大值。没有聪明的算法能帮你。。。除了避免创建powerset之外!
35g0bw7121#
以下解决方案是从我的书“编码面试:问题、分析和解决方案”中借用的:
数组中的一些整数被选中组成一个组合。使用一组位,其中每个位表示数组中的整数。如果选择第i个字符作为组合,则第i位为1;否则为0。例如,三位用于阵列的组合[1,2,3]。如果选择前两个整数1和2组成组合[1,2],则相应的位为{1,1,0}。类似地,对应于另一组合[1,3]的位是{1,0,1}。如果我们能得到n位的所有可能组合,我们就能得到长度为n的数组的所有组合。
数字是由一组位组成的。n位的所有可能组合对应于从1到2^n-1的数字。因此,在1和2^n-1之间的每个数字对应于长度为n的数组的组合。例如,数字6由位{1,1,0}组成,因此在数组[1,2,3]中选择第一个和第二个字符以生成组合[1,2]。类似地,位为{1,0,1}的数字5对应于组合[1,3]。
实现此解决方案的java代码如下所示:
方法增量增加以一组位表示的数字。该算法从最右边的位中清除1位,直到找到0位。然后将最右边的0位设置为1。例如,为了用位{1,0,1}增加数字5,它从右边清除1位,并将最右边的0位设置为1。数字6的位变成{1,1,0},这是5乘以1的结果。
xienkqul22#
这是我的递归解决方案,它可以使用java泛型获得任意集的幂集。其主要思想是将输入数组的头部与数组其余部分的所有可能解结合起来,如下所示。
这将输出:
643ylb0823#
另一个示例实现:
jaxagkaj24#
我们可以使用递归或不使用递归来编写幂集。下面是一个没有递归的尝试:
pbgvytdp25#
c7rzv4ha26#
我根据哈里的想法想出了另一个解决办法。可能不是最优雅的,但据我所知:
让我们以sp(s)={1},{2},{3}的经典简单例子powerset为例。我们知道得到子集数的公式是2^n(7+空集)。对于本例,2^3=8个子集。
为了找到每个子集,我们需要将0-7十进制转换为二进制表示,如下面的转换表所示:
如果我们逐行遍历表,每行将产生一个子集,每个子集的值将来自启用的位。
bin value部分中的每一列都对应于原始输入集中的索引位置。
这是我的密码: