Thursday Code Puzzler: Power Set Calculation
Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.
Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer. It's all about the participation!
Do you have code puzzlers that you'd like to share with the DZone community? If so, please submit here.
Power Sets
Write
a function that calculates all possible subsets of a given power set passed in as a array of Strings.
Catch up on all our previous puzzlers here.
Tags:
Comments
Daniel Seidler replied on Thu, 2012/12/13 - 5:54am
Kotlin
fun Array<String>.powerSet() = this.fold(setOf(setOf(): Set<String>)) {(set, el) -> set.union(set.map{it + el})} println(array("1","2","3").powerSet()) //[[3], [], [2], [3, 1], [1], [3, 2], [2, 1], [3, 2, 1]]Remigio Di Muzio replied on Sat, 2012/12/15 - 4:18am
private static Collection<Set<String>> calculateSubsets(String[] values) { int num = values.length; int max = 1 << num; Collection<Set<String>> subsets = new ArrayList<Set<String>>(max); for (int subset = 1; subset < max; ++subset) { subsets.add(calculateSubset(subset, values, num)); } return subsets; } private static Set<String> calculateSubset(int subset, String x[], int num) { Set<String> set = new HashSet<String>(); for (int j = 0; j < num; ++j) { if (((subset >> j) & 1) == 1) { set.add(x[j]); } } return set; }Erik Colban replied on Fri, 2012/12/14 - 2:58pm
where I use the notation a[i : j] to mean the sub array of a from i inclusive to k exclusive.public static String[][] power(String[] stringSet) { String[][] result = new String[1 << stringSet.length][]; result[0] = new String[0]; for (int i = 0, k = 1; i < stringSet.length; i++, k <<= 1) { // result[0 : k] is the powerset of stringSet[0 : i] for (int j = 0; j < k; j++) { int len = result[j].length; result[k + j] = new String[len + 1]; System.arraycopy(result[j], 0, result[k + j], 0, len); result[k + j][len] = stringSet[i]; } } return result; }Remigio Di Muzio replied on Sat, 2012/12/15 - 1:40pm
private static String[][] calculateSubsets(String[] values) { String[][] subsets = new String[1 << values.length][]; subsets[0] = new String[0]; for (int level = 1; level <= values.length; ++level) { int start = 1 << (level -1); int end = 1 << level; int prevStart = 0; for (int i = start, j = prevStart; i < end; ++i, ++ j) { subsets[i] = new String[subsets[j].length + 1]; addValueToSubset(subsets[j], subsets[i], values[level - 1]); } } return subsets; } private static void addValueToSubset(String[] sourceSubset, String[] destSubset, String value) { System.arraycopy(sourceSubset, 0, destSubset, 0, sourceSubset.length); destSubset[sourceSubset.length] = value; }Marco González replied on Wed, 2012/12/19 - 4:55pm
This is my idea. A simple iterative version.
I'm a new Python programmer, maybe I think as a C programmer...
def buildsubset(baseset, number): resultset = [] i = 0 while number > 0: m = number % 2 number = number // 2 if m == 1: resultset.append(baseset[i]) i = i + 1 return resultset def generatepowerset(baseset): powerset = [] n = 2 ** len(baseset) for i in range(0, n): powerset.append(buildsubset(baseset, i)) return powerset set1 = [ "one" , "two" , "three" , "four" ] pow_set1 = generatepowerset(set1) print pow_set1