I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Power Set Calculation

12.13.2012
| 3739 views |
  • submit to reddit

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.

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

It's tempting to use a recursive approach, but Java's array manipulation support is rather limited, so I went with an iterative approach instead. The outer for-loop is based on the following invariant:
  1. // result[0 : k] is the powerset of stringSet[0 : i]
    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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.