在 Java 中获取集合的幂集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1670862/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Obtaining a powerset of a set in Java
提问by Manuel Aráoz
The powerset of {1, 2, 3}is:
的幂集{1, 2, 3}为：
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
Let's say I have a Setin Java:
假设我Set在 Java 中有一个：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
How do I write the function getPowerset, with the best possible order of complexity? (I think it might be O(2^n).)
我如何编写函数 getPowerset，以尽可能复杂的顺序？（我认为它可能是 O(2^n)。）
采纳答案by Jo?o Silva
Yes, it is O(2^n)indeed, since you need to generate, well, 2^npossible combinations. Here's a working implementation, using generics and sets:
是的，O(2^n)确实如此，因为您需要生成2^n可能的组合。这是一个使用泛型和集合的工作实现：
public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
And a test, given your example input:
和一个测试，给定你的示例输入：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
System.out.println(s);
}
回答by Adamski
回答by Stephen C
If S is a finite set with N elements, then the power set of S contains 2^N elements. The time to simply enumerate the elements of the powerset is 2^N, so O(2^N)is a lower bound on the time complexity of (eagerly) constructing the powerset.
如果 S 是具有 N 个元素的有限集，则 S 的幂集包含 2^N 个元素。简单地枚举幂集元素的时间是 2^N，因此O(2^N)（热切地）构建幂集的时间复杂度的下限也是如此。
Put simply, any computation that involves creating powersets is not going to scale for large values of N. No clever algorithm will help you ... apart from avoiding the need to create the powersets!
简而言之，任何涉及创建幂集的计算都不会针对较大的 N 值进行缩放。没有聪明的算法可以帮助您......除了避免创建幂集的需要！
回答by Kevin Bourrillion
Actually, I've written code that does what you're asking for in O(1). The question is what you plan to dowith the Set next. If you're just going to call size()on it, that's O(1), but if you're going to iterate it that's obviously O(2^n).
实际上，我已经编写了在 O(1) 中执行您要求的代码。问题是你接下来打算用 Set做什么。如果你只是要调用size()它，那是 O(1)，但如果你要迭代它，那显然是O(2^n).
contains()would be O(n), etc.
contains()将是O(n)，等等。
Do you really need this?
你真的需要这个吗？
EDIT:
编辑：
This code is now available in Guava, exposed through the method Sets.powerSet(set).
此代码现在在 Guava 中可用，通过 方法公开Sets.powerSet(set)。
回答by st0le
Here's a solution where I use a generator, the advantage being, the entire power set is never stored at once... So you can iterate over it one-by-one without needing it to be stored in memory. I'd like to think it's a better option... Note the complexity is the same, O(2^n), but the memory requirements are reduced (assuming the garbage collector behaves! ;) )
这是我使用生成器的解决方案，优点是永远不会立即存储整个电源集......因此您可以逐个迭代它而无需将其存储在内存中。我想这是一个更好的选择...注意复杂性是相同的，O(2^n)，但内存需求减少了（假设垃圾收集器的行为！;)）
/**
*
*/
package org.mechaevil.util.Algorithms;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* @author st0le
*
*/
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set)
{
arr = (E[])set.toArray();
bset = new BitSet(arr.length + 1);
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
for(int i = 0; i < arr.length; i++)
{
if(bset.get(i))
returnSet.add(arr[i]);
}
//increment bset
for(int i = 0; i < bset.size(); i++)
{
if(!bset.get(i))
{
bset.set(i);
break;
}else
bset.clear(i);
}
return returnSet;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
}
To call it, use this pattern:
要调用它，请使用以下模式：
Set<Character> set = new TreeSet<Character> ();
for(int i = 0; i < 5; i++)
set.add((char) (i + 'A'));
PowerSet<Character> pset = new PowerSet<Character>(set);
for(Set<Character> s:pset)
{
System.out.println(s);
}
It's from my Project Euler Library... :)
它来自我的 Project Euler 库... :)
回答by Ben
I was looking for a solution that wasn't as huge as the ones posted here. This targets Java 7, so it will require a handful of pastes for versions 5 and 6.
我正在寻找一个不像这里发布的那样庞大的解决方案。这针对 Java 7，因此版本 5 和 6 需要一些粘贴。
Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
Set<Set<Object>> powerSet = new HashSet<>(),
runSet = new HashSet<>(),
thisSet = new HashSet<>();
while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
if (powerSet.isEmpty()) {
for (Object o : orig) {
Set<Object> s = new TreeSet<>();
s.add(o);
runSet.add(s);
powerSet.add(s);
}
continue;
}
for (Object o : orig) {
for (Set<Object> s : runSet) {
Set<Object> s2 = new TreeSet<>();
s2.addAll(s);
s2.add(o);
powerSet.add(s2);
thisSet.add(s2);
}
}
runSet.clear();
runSet.addAll(thisSet);
thisSet.clear();
}
powerSet.add(new TreeSet());
return powerSet;
Here's some example code to test:
这是一些要测试的示例代码：
Set<Object> hs = new HashSet<>();
hs.add(1);
hs.add(2);
hs.add(3);
hs.add(4);
for(Set<Object> s : powerSetofNodes(hs)) {
System.out.println(Arrays.toString(s.toArray()));
}
回答by Orestis
One way without recursion is the following: Use a binary mask and make all the possible combinations.
一种不使用递归的方法如下：使用二进制掩码并进行所有可能的组合。
public HashSet<HashSet> createPowerSet(Object[] array)
{
HashSet<HashSet> powerSet=new HashSet();
boolean[] mask= new boolean[array.length];
for(int i=0;i<Math.pow(2, array.length);i++)
{
HashSet set=new HashSet();
for(int j=0;j<mask.length;j++)
{
if(mask[i])
set.add(array[j]);
}
powerSet.add(set);
increaseMask(mask);
}
return powerSet;
}
public void increaseMask(boolean[] mask)
{
boolean carry=false;
if(mask[0])
{
mask[0]=false;
carry=true;
}
else
mask[0]=true;
for(int i=1;i<mask.length;i++)
{
if(mask[i]==true && carry==true)
mask[i]=false;
else if (mask[i]==false && carry==true)
{
mask[i]=true;
carry=false;
}
else
break;
}
}
回答by Harry He
The following solution is borrowed from my book "Coding Interviews: Questions, Analysis & Solutions":
以下解决方案是从我的《编码面试：问题、分析和解决方案》一书中借用的：
Some integers in an array are selected that compose a combination. A set of bits is utilized, where each bit stands for an integer in the array. If the i-thcharacter is selected for a combination, the i-thbit is 1; otherwise, it is 0. For instance, three bits are used for combinations of the array [1, 2, 3]. If the first two integers 1 and 2 are selected to compose a combination [1, 2], the corresponding bits are {1, 1, 0}. Similarly, bits corresponding to another combination [1, 3] are {1, 0, 1}. We are able to get all combinations of an array with length nif we can get all possible combinations of nbits.
选择数组中的一些整数组成一个组合。使用一组位，其中每一位代表数组中的一个整数。如果组合选择第i个字符，则第i位为1；否则为0。例如，数组[1,2,3]的组合使用三位。如果选择前两个整数1和2组成一个组合[1, 2]，则对应的位为{1, 1, 0}。类似地，另一个组合[1, 3]对应的位是{1, 0, 1}。如果我们可以获得n位的所有可能组合，我们就能够获得长度为n的数组的所有组合。
A number is composed of a set of bits. All possible combinations of nbits correspond to numbers from 1 to 2^n-1. Therefore, each number in the range between 1 and 2^n-1 corresponds to a combination of an array with length n. For example, the number 6 is composed of bits {1, 1, 0}, so the first and second characters are selected in the array [1, 2, 3] to generate the combination [1, 2]. Similarly, the number 5 with bits {1, 0, 1} corresponds to the combination [1, 3].
一个数字由一组位组成。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]。
The Java code to implement this solution looks like below:
实现此解决方案的 Java 代码如下所示：
public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) {
ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>();
BitSet bits = new BitSet(numbers.length);
do{
combinations.add(getCombination(numbers, bits));
}while(increment(bits, numbers.length));
return combinations;
}
private static boolean increment(BitSet bits, int length) {
int index = length - 1;
while(index >= 0 && bits.get(index)) {
bits.clear(index);
--index;
}
if(index < 0)
return false;
bits.set(index);
return true;
}
private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){
ArrayList<Integer> combination = new ArrayList<Integer>();
for(int i = 0; i < numbers.length; ++i) {
if(bits.get(i))
combination.add(numbers[i]);
}
return combination;
}
The method increment increases a number represented in a set of bits. The algorithm clears 1 bits from the rightmost bit until a 0 bit is found. It then sets the rightmost 0 bit to 1. For example, in order to increase the number 5 with bits {1, 0, 1}, it clears 1 bits from the right side and sets the rightmost 0 bit to 1. The bits become {1, 1, 0} for the number 6, which is the result of increasing 5 by 1.
方法增量增加以一组位表示的数字。该算法从最右边的位开始清除 1 位，直到找到 0 位。然后将最右边的 0 位设置为 1。例如，为了用位 {1, 0, 1} 增加数字 5，它从右边清除 1 位并将最右边的 0 位设置为 1。这些位变为{1, 1, 0} 表示数字 6，这是 5 加 1 的结果。
回答by George Fairbanks
Some of the solutions above suffer when the size of the set is large because they are creating a lot of object garbage to be collected and require copying data. How can we avoid that? We can take advantage of the fact that we know how big the result set size will be (2^n), preallocate an array that big, and just append to the end of it, never copying.
当集合的大小很大时，上面的一些解决方案会受到影响，因为它们会创建大量要收集的对象垃圾并需要复制数据。我们怎样才能避免这种情况？我们可以利用我们知道结果集大小有多大 (2^n) 的事实，预先分配一个那么大的数组，然后附加到它的末尾，从不复制。
The speedup grows quickly with n. I compared it to Jo?o Silva's solution above. On my machine (all measurements approximate), n=13 is 5x faster, n=14 is 7x, n=15 is 12x, n=16 is 25x, n=17 is 75x, n=18 is 140x. So that garbage creation/collection and copying is dominating in what otherwise seem to be similar big-O solutions.
加速比随着 n 快速增长。我将它与上面 Jo?o Silva 的解决方案进行了比较。在我的机器上（所有测量值都是近似值），n=13 快 5x，n=14 是 7x，n=15 是 12x，n=16 是 25x，n=17 是 75x，n=18 是 140x。因此，垃圾创建/收集和复制在其他看似类似的大 O 解决方案中占主导地位。
Preallocating the array at the beginning appears to be a win compared to letting it grow dynamically. With n=18, dynamic growing takes about twice as long overall.
与让它动态增长相比，在开始时预分配数组似乎是一个胜利。当 n=18 时，动态增长的总体时间大约是其两倍。
public static <T> List<List<T>> powerSet(List<T> originalSet) {
// result size will be 2^n, where n=size(originalset)
// good to initialize the array size to avoid dynamic growing
int resultSize = (int) Math.pow(2, originalSet.size());
// resultPowerSet is what we will return
List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);
// Initialize result with the empty set, which powersets contain by definition
resultPowerSet.add(new ArrayList<T>(0));
// for every item in the original list
for (T itemFromOriginalSet : originalSet) {
// iterate through the existing powerset result
// loop through subset and append to the resultPowerset as we go
// must remember size at the beginning, before we append new elements
int startingResultSize = resultPowerSet.size();
for (int i=0; i<startingResultSize; i++) {
// start with an existing element of the powerset
List<T> oldSubset = resultPowerSet.get(i);
// create a new element by adding a new item from the original list
List<T> newSubset = new ArrayList<T>(oldSubset);
newSubset.add(itemFromOriginalSet);
// add this element to the result powerset (past startingResultSize)
resultPowerSet.add(newSubset);
}
}
return resultPowerSet;
}
回答by Andrew Mao
If n < 63, which is a reasonable assumption since you'd run out of memory (unless using an iterator implementation) trying to construct the power set anyway, this is a more concise way to do it. Binary operations are way faster than Math.pow()and arrays for masks, but somehow Java users are afraid of them...
如果 n < 63，这是一个合理的假设，因为无论如何您都会用尽内存（除非使用迭代器实现）尝试构造幂集，这是一种更简洁的方法。二元运算比Math.pow()掩码数组快得多，但不知何故Java用户害怕它们......
List<T> list = new ArrayList<T>(originalSet);
int n = list.size();
Set<Set<T>> powerSet = new HashSet<Set<T>>();
for( long i = 0; i < (1 << n); i++) {
Set<T> element = new HashSet<T>();
for( int j = 0; j < n; j++ )
if( (i >> j) % 2 == 1 ) element.add(list.get(j));
powerSet.add(element);
}
return powerSet;
