Erik has a long history of experience in telecommunication standards development and participation in standard organizations. Erik has posted 1 posts at DZone. You can read more from them at their website. View Full User Profile

DZone Code Puzzler Follow-up: Power Set - Round 2

01.05.2013
| 1968 views |
  • submit to reddit

On Dec. 13, the code puzzler was to generate the power set of a set provided as an array of strings. The puzzler did not specify which data representation we were supposed to use for the power set. Like others who submitted a solution I assumed that the power set was to be represented as an array of string arrays. However, this is bad for the following two reasons:

  1. The length of an array is an int, which limits the length of the given set to 30. (The largest positive int is 2 ^ 31 - 1.)
  2. Even if the length of the given set is less than 31, one runs the risk of running out of memory.

So, rather than representing the power set as an array, define a class PowerSet and let instances of this class be representations of the power sets. The constructor should take a string array as argument, and the class should have at least the following methods:

  • size() // returns the size of the power set as a long (64 bit signed)
  • get(long i) : returns the i'th subset

In particular, the following code should print out all the singletons of the power set:


String[] set = new String[] { "a", "b", "c", "d", "e", "f", "g", "h",
				"i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
				"u", "v", "w", "x", "y", "z", "A", "B", "C", "D", "E", "F",
				"G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R",
				"S", "T", "U", "V", "W", "X", "Y", "Z", "0", "1", "2", "3",
				"4", "5", "6", "7", "8", "9" };
		PowerSet ps = new PowerSet(set);
		for (long i = 1; i < ps.size(); i <<= 1) {
			System.out.println(Arrays.toString(ps.get(i)));
		}

 ------- This line and below is intended for the arbitrator only ----

Since the largest positive long is 2 ^ 63 - 1, and the size of the power set is a power of 2, the size of the power set is limited to 2 ^ 62. Each subset can be represented by a long; if the i'th bit is 1, the i'th element of given set is an element of this subset. The get method simply converts between this representation and a String[] representation as shown below:

public String[] get(long index) throws IndexOutOfBoundsException {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		int count = 0;
		// count the number of elements in the subset
		for (int i = 0; i < set.length; i++) {
			count += index >> i & 1;
		}
		String[] result = new String[count];
		count = 0;
		// Add the elements to the result
		for (int i = 0; i < set.length; i++) {
			if ((index >> i & 1) == 1) {
				result[count++] = set[i];
			}
		}
		return result;
	}
Published at DZone with permission of its author, Erik Colban.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)