Generating all subsets of a given set

Question

I am learning Java Collections Framework. Can someone look at this code for generating all subsets of a given set and tell me any issues with it.

import java.util.*;
public class AllSubsets {
 public static void main(String[] args) {
 Set<Integer> original = new HashSet<Integer>();
 for (int i = Integer.parseInt(args[0]); i > 0; i--) {
 original.add(i);
 } 
 System.out.println(generateAllSubsets(original));
 }
 public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {
 HashSet<HashSet<Integer>> allSubsets = new HashSet<HashSet<Integer>>();
 allSubsets.add(new HashSet<Integer>()); //Add empty set.
 Iterator it = original.iterator();
 while(it.hasNext()) {
 Integer element = (Integer) it.next();
 //Deep copy all subsets to temporary power set.
 HashSet<HashSet<Integer>> tempClone = new HashSet<HashSet<Integer>>();
 for (HashSet<Integer> subset : allSubsets) {
 tempClone.add((HashSet<Integer>)subset.clone());
 } 
 //All element to all subsets of the temporary power set.
 Iterator it2 = tempClone.iterator();
 while(it2.hasNext()) {
 Set<Integer> s = (HashSet<Integer>) it2.next();
 s.add(element);
 } 
 //Merge both power sets.
 allSubsets.addAll(tempClone);
 } 
 return allSubsets;
 }
}

• Alexei Kaigorodov: you use vague algorithm, so no one wish to decrypt and and thus you received no answer. To represent a subset, usually an integer in binary representation is used: 0 in a given position means element is absent, 1 - present. To generate all subsets, start with 0 and add 1, counting all integers up to 2^N-1. If you have less than 64 elements, you can use long integer, other wise use BitSet, and implement operation of adding 1.
• Peter Taylor: @AlexeiKaigorodov, how can an implementation in an actual language be a "vague algorithm"? Pseudocode can be vague, but this isn't.
• Anirban Nag 'tintinmj': Guava has same kind of method and check also in SO

Answer 1

The first, obvious, issue is that generating the set in memory uses a lot of memory. However, making a lazy version is a bit more advanced, so don't worry about it for now.

1. Code to the interface, not the implementation

public static HashSet<HashSet<Integer>> generateAllSubsets(Set<Integer> original) {

is bad.

public static Set<Set<Integer>> generateAllSubsets(Set<Integer> original) {

is better.

2. Generics reduce repetition

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {

is better still, because you can use it to find power sets of any set.

3. Generics remove the necessity to do most casts

 Iterator it = original.iterator();
 while(it.hasNext()) {
 Integer element = (Integer) it.next();

and

 Iterator it2 = tempClone.iterator();
 while(it2.hasNext()) {
 Set<Integer> s = (HashSet<Integer>) it2.next();

have wholly unnecessary explicit casts (which in the second case generates a warning) because you're using the raw type Iterator. Both can also be simplified using the same foreach syntax which you use when making the copy of the power set so far.

4. KISS

You have three loops (including the one hidden behind allSubsets.addAll), which seems to me to be unnecessarily complicated. If you make a shallow copy first then you can combine the deep copy with the adding an element.

public static <T> Set<Set<T>> generateAllSubsets(Set<T> original) {
 Set<Set<T>> allSubsets = new HashSet<Set<T>>();
 allSubsets.add(new HashSet<T>()); //Add empty set.
 for (T element : original) {
 // Copy subsets so we can iterate over them without ConcurrentModificationException
 Set<Set<T>> tempClone = new HashSet<Set<T>>(allSubsets);
 // All element to all subsets of the current power set.
 for (Set<T> subset : tempClone) {
 Set<T> extended = new HashSet<T>(subset);
 extended.add(element);
 allSubsets.add(extended);
 }
 }
 return allSubsets;
}

You'll note that I'm using the copy-constructor rather than clone(). That's a matter of taste: fundamentally there's no real difference, because they're both special-cased.