Platinum Partner
architects,computer science,code puzzler,puzzler

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

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;
	}
{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}