在Java中获取集合的powerset
{1, 2, 3}是：
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
假设我有一个Java Set ：
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））。
是的，确实是O(2^n) ，因为你需要生成2^n可能的组合。 这是一个工作实现，使用generics和集合：
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; }
和一个testing，给你的例子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); }
实际上，我已经写了一些代码来完成你在O（1）中所要求的。 问题在于你打算如何处理Set。 如果你只是要调用size() ，那就是O（1），但是如果你要迭代它，显然是O(2^n) 。
contains()是O(n)等
你真的需要这个吗？
编辑：
这个代码现在在Guava中可用 ，通过Sets.powerSet(set)方法暴露。
这里有一个解决scheme，我使用一个发生器，好处是整个功耗集不会一次存储…所以你可以一个接一个地迭代它，而不需要把它存储在内存中。 我想这是一个更好的select…注意复杂度是相同的，O（2 ^ n），但是内存需求减less了（假设垃圾收集器的行为！））
/** * */ 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; } }
要调用它，使用这种模式：
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); }
这是从我的项目欧拉图书馆… 🙂
这里是一个教程，确切地描述你想要的，包括代码。 你是正确的，复杂性是O（2 ^ n）。
如果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;
我想出了另一个基于@Harry他的想法的解决scheme。 可能不是最优雅的，但在这里，我了解它：
我们来看SP（S）= {{1}，{2}，{3}}的经典简单例子PowerSet。 我们知道得到子集数的公式是2 ^ n（7 +空集）。 对于这个例子2 ^ 3 = 8个子集。
为了find每个子集，我们需要将0-7十进制转换为以下转换表中所示的二进制表示forms：
如果我们逐行遍历表，每行将产生一个子集，每个子集的值将来自使能位。
Bin Value部分中的每个列对应于原始inputSet中的索引位置。
在这里我的代码：
public class PowerSet { /** * @param args */ public static void main(String[] args) { PowerSet ps = new PowerSet(); Set<Integer> set = new HashSet<Integer>(); set.add(1); set.add(2); set.add(3); for (Set<Integer> s : ps.powerSet(set)) { System.out.println(s); } } public Set<Set<Integer>> powerSet(Set<Integer> originalSet) { // Original set size eg 3 int size = originalSet.size(); // Number of subsets 2^n, eg 2^3 = 8 int numberOfSubSets = (int) Math.pow(2, size); Set<Set<Integer>> sets = new HashSet<Set<Integer>>(); ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet); for (int i = 0; i < numberOfSubSets; i++) { // Get binary representation of this index eg 010 = 2 for n = 3 String bin = getPaddedBinString(i, size); //Get sub-set Set<Integer> set = getSet(bin, originalList)); sets.add(set); } return sets; } //Gets a sub-set based on the binary representation. Eg for 010 where n = 3 it will bring a new Set with value 2 private Set<Integer> getSet(String bin, List<Integer> origValues){ Set<Integer> result = new HashSet<Integer>(); for(int i = bin.length()-1; i >= 0; i--){ //Only get sub-sets where bool flag is on if(bin.charAt(i) == '1'){ int val = origValues.get(i); result.add(val); } } return result; } //Converts an int to Bin and adds left padding to zero's based on size private String getPaddedBinString(int i, int size) { String bin = Integer.toBinaryString(i); bin = String.format("%0" + size + "d", Integer.parseInt(bin)); return bin; } }
如果您正在使用Eclipse集合 （以前称为GS集合 ），则可以在所有SetIterables上使用powerSet()方法。
MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3); System.out.println("powerSet = " + set.powerSet()); // prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
注意：我是Eclipse集合的提交者。
我正在寻找一个不像在这里发布的那么大的解决scheme。 这个目标是针对Java 7的，所以它需要less量的版本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;
以下是一些要testing的示例代码：
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())); }
以下解决scheme是从我的书“ Coding Interviews：Questions，Analysis＆Solutions ”中借用的：
select一个数组中的一些整数组成一个组合。 使用一组位，其中每个位代表数组中的整数。 如果第i个字符被select用于组合，则第i位是1; 否则为0.例如，三位用于数组[1,2,3]的组合。 如果select前两个整数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]中select第一个和第二个字符来生成组合[1,2]。 类似地，具有比特{1,0,1}的数字5对应于组合[1,3]。
实现此解决scheme的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; }
方法增量增加了以一组位表示的数字。 algorithm从最右边的位清除1位，直到find0位。 然后它将最右边的0位设置为1.例如，为了增加位数为{1,0,1}的数字5，它从右边清除1位，并将最右边的0位设置为1。数字6的{1，1，0}，这是5乘1的结果。
上面的一些解决scheme在集合的大小很大时会受到影响，因为它们会创build大量的要收集的对象垃圾并需要复制数据。 我们怎样才能避免呢？ 我们可以利用这样一个事实，即我们知道结果集的大小将是多less（2 ^ n），预先分配一个很大的数组，并且只是追加到最后，从不复制。
n加速增长。 我将它与上面的JoãoSilva的解决scheme进行了比较。 在我的机器上（所有测量值近似），n = 13是5倍快，n = 14是7倍，n = 15是12倍，n = 16是25倍，n = 17是75倍，n = 18是140倍。 所以垃圾的创build/收集和复制主要是在类似的大O解决scheme。
在开始分配数组看起来是一个胜利，而不是让它dynamic增长。 n = 18时，dynamic增长需要大约两倍的时间。
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; }
这是一个简单的迭代O（2 ^ n）解决scheme：
public static Set<Set<Integer>> powerSet(List<Integer> intList){ Set<Set<Integer>> result = new HashSet(); result.add(new HashSet()); for (Integer i : intList){ Set<Set<Integer>> temp = new HashSet(); for(Set<Integer> intSet : result){ intSet = new HashSet(intSet); intSet.add(i); temp.add(intSet); } result.addAll(temp); } return result; }
import java.util.Set; import com.google.common.collect.*; Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));
如果S是有N个元素的有限集，则S的幂集包含2 ^ N个元素。 简单地列举权力元素的时间是2 ^ N，所以O(2^N)是（急切地）构build权力的时间复杂度的下界。
简而言之，任何涉及创build电源的计算都不会针对N的大数值进行调整。没有聪明的algorithm可以帮助您…除了避免创build电源之外！
没有recursion的一种方法如下：使用二进制掩码并进行所有可能的组合。
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; } }
algorithm：
input：Set []，set_size 1获取功率集的大小powet_set_size = pow（2，set_size）2从0到pow_set_size的计数器循环（a）i = 0的循环到set_size（i）如果计数器中的第i位是设置为这个子集打印第i个元素集（b）为子集打印分隔符，即换行符
#include <stdio.h> #include <math.h> void printPowerSet(char *set, int set_size) { /*set_size of power set of a set with set_size n is (2**n -1)*/ unsigned int pow_set_size = pow(2, set_size); int counter, j; /*Run from counter 000..0 to 111..1*/ for(counter = 0; counter < pow_set_size; counter++) { for(j = 0; j < set_size; j++) { /* Check if jth bit in the counter is set If set then pront jth element from set */ if(counter & (1<<j)) printf("%c", set[j]); } printf("\n"); } } /*Driver program to test printPowerSet*/ int main() { char set[] = {'a','b','c'}; printPowerSet(set, 3); getchar(); return 0; }
这是我的recursion解决scheme，可以使用Java Generics获得任何设置的权力集。 它的主要思想是将input数组的头部与其余数组的所有可能的解决scheme组合如下。
import java.util.LinkedHashSet; import java.util.Set; public class SetUtil { private static<T> Set<Set<T>> combine(T head, Set<Set<T>> set) { Set<Set<T>> all = new LinkedHashSet<>(); for (Set<T> currentSet : set) { Set<T> outputSet = new LinkedHashSet<>(); outputSet.add(head); outputSet.addAll(currentSet); all.add(outputSet); } all.addAll(set); return all; } //Assuming that T[] is an array with no repeated elements ... public static<T> Set<Set<T>> powerSet(T[] input) { if (input.length == 0) { Set <Set<T>>emptySet = new LinkedHashSet<>(); emptySet.add(new LinkedHashSet<T>()); return emptySet; } T head = input[0]; T[] newInputSet = (T[]) new Object[input.length - 1]; for (int i = 1; i < input.length; ++i) { newInputSet[i - 1] = input[i]; } Set<Set<T>> all = combine(head, powerSet(newInputSet)); return all; } public static void main(String[] args) { Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6}); System.out.println(set); } }
这将输出：
[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []]
这是我用lambdaexpression的方法。
public static <T> Set<Set<T>> powerSet(T[] set) { return IntStream .range(0, (int) Math.pow(2, set.length)) .parallel() //performance improvement .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet())) .map(Function.identity()) .collect(Collectors.toSet()); }
或者并行（参见parallel（）注释）：
input大小：18
逻辑处理器：8？3.4GHz
性能提升：30％
// input: S // output: P // S = [1,2] // P = [], [1], [2], [1,2] public static void main(String[] args) { String input = args[0]; String[] S = input.split(","); String[] P = getPowerSet(S); if (P.length == Math.pow(2, S.length)) { for (String s : P) { System.out.print("[" + s + "],"); } } else { System.out.println("Results are incorrect"); } } private static String[] getPowerSet(String[] s) { if (s.length == 1) { return new String[] { "", s[0] }; } else { String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length)); String[] subP2 = new String[subP1.length]; for (int i = 0; i < subP1.length; i++) { subP2[i] = s[0] + subP1[i]; } String[] P = new String[subP1.length + subP2.length]; System.arraycopy(subP1, 0, P, 0, subP1.length); System.arraycopy(subP2, 0, P, subP1.length, subP2.length); return P; } }
我最近不得不使用类似这样的东西，但首先需要最小的子列表（有1个元素，然后是2个元素，…）。 我不想列入空白列表或整个列表。 另外，我不需要列出所有返回的子列表，我只需要在每个子列表上做一些事情。
想要做这个没有recursion，并提出以下（与“做东西”抽象为function接口）：
@FunctionalInterface interface ListHandler<T> { void handle(List<T> list); } public static <T> void forAllSubLists(final List<T> list, ListHandler handler) { int ll = list.size(); // Length of original list int ci[] = new int[ll]; // Array for list indices List<T> sub = new ArrayList<>(ll); // The sublist List<T> uml = Collections.unmodifiableList(sub); // For passing to handler for (int gl = 1, gm; gl <= ll; gl++) { // Subgroup length 1 .. n-1 gm = 0; ci[0] = -1; sub.add(null); // Some inits, and ensure sublist is at least gl items long do { ci[gm]++; // Get the next item for this member if (ci[gm] > ll - gl + gm) { // Exhausted all possibilities for this position gm--; continue; // Continue with the next value for the previous member } sub.set(gm, list.get(ci[gm])); // Set the corresponding member in the sublist if (gm == gl - 1) { // Ok, a sublist with length gl handler.handle(uml); // Handle it } else { ci[gm + 1] = ci[gm]; // Starting value for next member is this gm++; // Continue with the next member } } while (gm >= 0); // Finished cycling through all possibilities } // Next subgroup length }
这样，也很容易将其限制在特定长度的子列表中。
另一个示例实现：
public static void main(String args[]) { int[] arr = new int[]{1,2,3,4}; // Assuming that number of sets are in integer range int totalSets = (int)Math.pow(2,arr.length); for(int i=0;i<totalSets;i++) { String binaryRep = Integer.toBinaryString(i); for(int j=0;j<binaryRep.length();j++) { int index=binaryRep.length()-1-j; if(binaryRep.charAt(index)=='1') System.out.print(arr[j] +" "); } System.out.println(); } }
public class PowerSet { public static List<HashSet<Integer>> powerset(int[] a) { LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>(); int n = a.length; for (int i = 0; i < 1 << n; i++) { HashSet<Integer> set = new HashSet<Integer>(); for (int j = 0; j < n; j++) { if ((1 << j & i) > 0) set.add(a[j]); } sets.add(set); } return sets; } public static void main(String[] args) { List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 }); for (HashSet<Integer> set : sets) { for (int i : set) System.out.print(i); System.out.println(); } } }
另一个解决scheme – 用java8 + streaming api它是惰性的，并且是有序的，因此当它与“limit（）”一起使用时，它会返回正确的子集。
public long bitRangeMin(int size, int bitCount){ BitSet bs = new BitSet(size); bs.set(0, bitCount); return bs.toLongArray()[0]; } public long bitRangeMax(int size, int bitCount){ BitSet bs = BitSet.valueOf(new long[]{0}); bs.set(size - bitCount, size); return bs.toLongArray()[0]; } public <T> Stream<List<T>> powerSet(Collection<T> data) { List<T> list = new LinkedHashSet<>(data).stream().collect(Collectors.toList()); Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i})); Stream<BitSet> tail = IntStream.rangeClosed(1, list.size()) .boxed() .flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1)) .mapToObj(v2 -> BitSet.valueOf(new long[]{v2})) .filter( bs -> bs.cardinality() == v1)); return Stream.concat(head, tail) .map( bs -> bs .stream() .mapToObj(list::get) .collect(Collectors.toList())); }
而客户端代码是
@Test public void testPowerSetOfGivenCollection(){ List<Character> data = new LinkedList<>(); for(char i = 'a'; i < 'a'+5; i++ ){ data.add(i); } powerSet(data) .limit(9) .forEach(System.out::print); }
/ *打印：[] [a] [b] [c] [d] [e] [a，b] [a，c] [b，c] * /
我们可以使用或不使用recursion来编写权力集合。 这是一个没有recursion的尝试：
public List<List<Integer>> getPowerSet(List<Integer> set) { List<List<Integer>> powerSet = new ArrayList<List<Integer>>(); int max = 1 << set.size(); for(int i=0; i < max; i++) { List<Integer> subSet = getSubSet(i, set); powerSet.add(subSet); } return powerSet; } private List<Integer> getSubSet(int p, List<Integer> set) { List<Integer> subSet = new ArrayList<Integer>(); int position = 0; for(int i=p; i > 0; i >>= 1) { if((i & 1) == 1) { subSet.add(set.get(position)); } position++; } return subSet; }
