Write a method that returns all subsets of a set

Write a method that returns all subsets of a set.

My initial thoughts:
Suppose we need to find the subsets of a set A with size k, where \left| A \right|=n. We can scan every elements a_{i} in A and choose either to pick a_{i} or not. If we pick a_{i}, we need to find another k-1 elements in the set A - \{a_{i}\}. If we do not choose a_{i}, we need to find another k elements in the set A - \{a_{i}\}.
We can then find all subsets of A by iterating k through 0 to n.

My initial codes:

	public static Set<Set<Character>> AllSubset
						(Set<Character> elements) {
		Set<Set<Character>> results = 
				new HashSet<Set<Character>>();

		for (int i = 0; i <= elements.size(); ++i) {
			Set<Set<Character>> temp = 
					new HashSet<Set<Character>>();
			KSubsets(elements, new HashSet<Character>(), 
					temp, i);
			results.addAll(temp);
		}
		return results;
	}

	public static void KSubsets(Set<Character> elements, 
			Set<Character> subset,
			Set<Set<Character>> results, int k) {
		if (k > elements.size())
			return;
		if (elements.size() == 0 || k == 0) {
			Set<Character> putin = new HashSet<Character>();
			for (Character o : subset)
				putin.add(o);
			results.add(putin);
			subset = new HashSet<Character>();
			return;
		}
		// include 1st element, choose k-1 element 
		// from the remaining n-1 elements
		Character o = elements.iterator().next();
		subset.add(o); // subset = {..., o}
		Set<Character> newElements = new HashSet<Character>();
		for (Character c : elements)
			if (!c.equals(o))
				newElements.add(c);
		KSubsets(newElements, subset, results, k - 1);

		// exclude 1st element, choose k element
		// from the remaining n-1 elements
		subset.remove(o); // subset = {...}
		newElements = new HashSet<Character>();
		for (Character c : elements)
			if (!c.equals(o))
				newElements.add(c);
		KSubsets(newElements, subset, results, k);
	}

Solution:

  1. Recursion:
    This is a great problem to implement with recursion since we can build all subsets of a set using all subsets of a smaller set. Specifically, given a set S, we can do the following recursively:

    • Let first = S[0]; Let smallerSet = S[1 ,…, n]
    • Compute all subsets of smallerSet and put them in allsubsets
    • For each subset in allsubsets, clone it and add first to the subset
    	ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, 
    			int index) {
    		ArrayList<ArrayList<Integer>> allsubsets;
    		if (set.size() == index) {
    			allsubsets = new ArrayList<ArrayList<Integer>>();
    			allsubsets.add(new ArrayList<Integer>()); // Empty set
    		} else {
    			allsubsets = getSubsets(set, index + 1);
    			int item = set.get(index);
    			ArrayList<ArrayList<Integer>> moresubsets = 
    					new ArrayList<ArrayList<Integer>>();
    			for (ArrayList<Integer> subset : allsubsets) {
    				ArrayList<Integer> newsubset = 
    						new ArrayList<Integer>();
    				newsubset.addAll(subset); //
    				newsubset.add(item);
    				moresubsets.add(newsubset);
    			}
    			allsubsets.addAll(moresubsets);
    		}
    		return allsubsets;
    	}
    
  2. Combinatorics:
    • When we’re generating a set, we have two choices for each element: (1) the element is in the set (the “yes” state) or (2) the element is not in the set (the “no” state). This means that each subset is a sequence of yesses/nos — e.g., “yes, yes, no, no, yes, no”.
    • This gives us 2^{n} possible subsets. How can we iterate through all possible sequences of “yes”/”no” states for all elements? If each “yes” can be treated as a 1 and each “no” can be treated as a 0, then each subset can be represented as a binary string.
    • Generating all subsets then really just comes down to generating all binary numbers (that is, all integers). Easy!
    	ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {
    		ArrayList<ArrayList<Integer>> allsubsets = 
    				new ArrayList<ArrayList<Integer>>();
    		int max = 1 << set.size();
    		for (int i = 0; i < max; i++) {
    			ArrayList<Integer> subset = new ArrayList<Integer>();
    			int k = i;
    			int index = 0;
    			while (k > 0) {
    				if ((k & 1) > 0) {
    					subset.add(set.get(index));
    				}
    				k >>= 1;
    				index++;
    			}
    			allsubsets.add(subset);
    		}
    		return allsubsets;
    	}
    
Advertisements

1 Comment (+add yours?)

  1. Trackback: Questions : Job Hunting

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: