Generate powerset in JS

Question

I came across a mock interview question in which the candidate is asked to generate the powerset of a given set.

The input set is represented as a unique array of integers.

There was no solution provided in this instance, so I tried to see what i could come up with on my own. I did struggle my way to a solution and I'm not particularly dissatisfied with it, but I'm not particularly satisfied either.

I took a recursive approach. Essentially, I generated a tree, depth first, with the uppermost level consisting of the original set and each successive lower level consisting of the immediate subsets of the parent node.

Here's my code. I am using ES5.

    var result = generate_powerset([1, 2, 3, 4]);
    console.log(result);

    function generate_powerset(set) {
      var powerset = generate_subsets(set);
      powerset.push(set);
      return powerset;
    }

    function generate_subsets(set) {
      var subsets = [];
      set.forEach(function(element, i) {
        var immediate_subset = remove_index(set, i);
        maybe_push(subsets, immediate_subset);
        var extended_subsets = generate_subsets(immediate_subset);
        extended_subsets.forEach(function(extended_subset) {
          maybe_push(subsets, extended_subset);
        });
      });
      return subsets;
    }

    function remove_index(array, i) {
      return array.filter(function(el, j) {
        return i != j;
      });
    }

    function maybe_push(set, non_member) {
      var already_member = false;
      set.forEach(function(member) {
        if (are_identical(member, non_member)) already_member = true;
      })
      if (!already_member) set.push(non_member);
    }

    function are_identical(set1, set2) {
      return (JSON.stringify(set1.sort()) == JSON.stringify(set2.sort()));
    }

I'm looking for ways to:

• Make this algorithm more efficient
• Make this code easier to understand
• Make my code shorter

I'm also just generally curious if this approach is considered orthodox or unorthodox.

Answer 1

Here's another take on the powerset algorithm:

function powerset(l) {
    // TODO: ensure l is actually array-like, and return null if not
    return (function ps(list) {
        if (list.length === 0) {
            return [[]];
        }
        var head = list.pop();
        var tailPS = ps(list);
        return tailPS.concat(tailPS.map(function(e) { return [head].concat(e); }));
    })(l.slice());
}

// Test cases:
console.log(powerset([1,2,3,4]));
console.log(powerset([10,30,20]));

It works by using the following inductive observation:

$$\mathcal{P}(X \cup \{e\})=\mathcal{P}(X)\cup\left\{\{e\} \cup Y~|~Y \in \mathcal{P}(X)\right\}$$

Basically, the powerset of any set X plus another element is the powerset of X along with another copy of the powerset where every set contains the element. Concisely, every element is either in a subset or not. This recurrence captures that "obvious" statement.

To specifically critique your code: given the method above, there's no reason to do a quadratic (well, exponential in the input) scan for duplicates, so this will be much more efficient. No need for JSON conversions, which take time, too. Since JavaScript is dynamically typed, you would need to put some handling code for invalid types passed into the function. These can be done before the anonymous-function-call-return gadget (which preserves the input); see the TODO in my code above.

The lack of sorting, JSON conversion, and de-duplication allows this code to create a powerset of 20 elements quickly, whereas the implementation in your question crashes Chrome.

Answer 2

I suggest this solution:

console.log(powerset([1, 2, 3, 4]));

function powerset(set, result) {
  if (!result) {
    var begin = true;
    result = [];
  }
  if (set.length) {
    result = set.reduce(function(result, current, index, array) {
      var subset = array.slice(0);
      result.push(JSON.stringify(subset.splice(index, 1)));
      powerset(subset, result);
      return result;
    }, result);
  }
  result.push(JSON.stringify(set));
  if (begin) {
    result = result
      .reduce(function(result, current) {
        if (result.indexOf(current) == -1) {
          result.push(current);
        }
        return result;
      }, [])
      .map(function(current) {
        return JSON.parse(current);
      });
  }
  return result;
}

Regarding your three points:

Make this algorithm more efficient

Actually the one used in my proposed code is not quite different:

• like yours, it successively processes each member of the given set, recursively sub-processing the set of all other members
• and like yours it uses JSON.stringify on each resulting member to avoid duplicates

Make this code easier to understand

Here are the main differences:

• there is a unique function, and the whole main process part is very compact:

  if (set.length) { result = set.reduce(function(result, current, index, array) { var subset = array.slice(0); result.push(JSON.stringify(subset.splice(index, 1))); powerset(subset, result); return result; }, result); } result.push(JSON.stringify(set));
  From the current set, it pushes into result each of its members, recursively sub-processes the subset of all other members, and finally pushes the entire set itself.

• also it pushes JSON.stringified members instead of the original members: this way, it becomes easy to drop duplicates at end, before turning members back to their real value in the final result.

Make my code shorter

It results in a much more concise code. Note that, ironically, the final cleaning process uses more lines than the main process! I hope this might be improved to end with a yet more recuded code.

Answer 3

The overall readability can be improved. As to efficiency you could remove the outer forEach and use a concat. Also the check for similarity is not necessary. Here below 3 alternative solutions, using different language primitives which make for better readability and a bit better efficiency.

1. Solution I: somewhat easier to read as it includes a visible for loop and explicit build up of a tmp array

var findPowerSet = function(input) {
    if(input.length === 0) return [input];
    
    let first = input[0];
    let rest = findPowerSet(input.slice(1));
    
    let tmp = [];
    for(let i=0; i<rest.length;i++) {
        tmp.push([first].concat(rest[i]));
    }
    
    return tmp.concat(rest);

};

let input = [1,2,3];

console.log(`input: ${JSON.stringify(input)}, result: ${JSON.stringify(findPowerSet(input))}`)

2. Solution II: Shorter solution, still easy to read as it involves forEach method

var findPowerSet = function(input) {
    if(input.length === 0) return [input];
    
    let first = input[0];
    let rest = findPowerSet(input.slice(1));
    
    let tmp = [];
    
    rest.forEach(el => tmp.push([first].concat(el)));
    
    return tmp.concat(rest);

};

let input = [1,2,3];

console.log(`input: ${JSON.stringify(input)}, result: ${JSON.stringify(findPowerSet(input))}`)

3. Solution III: Even shorter solution, however, requires knowledge of JS map() method:

var findPowerSet = function(input) {
    if(input.length === 0) return [input];
    
    let first = input[0];
    let rest = findPowerSet(input.slice(1));
    
    let tmp = rest.map(el => [first].concat(el));
    
    return tmp.concat(rest);

};

let input = [1,2,3];

console.log(`input: ${JSON.stringify(input)}, result: ${JSON.stringify(findPowerSet(input))}`)

Here is an explanation of the recursion process:

        {1,2,3}
     {1}    {2,3}
   {}    {2}   {3}
end    {}     {}
     end    end

• base case '{}' return [[]]
• recursion case:
  1. take the first element of a set
  2. recurse for the tail (rest of the set)
  3. add the first element from step 1 to each element of the rest of the set from step2
  4. return concatenated the result of step 3 with the rest, so combine the result of all recursions

Time complexity: O(2^N) - exponential (as can be observed from the recursion tree)

Space complexity: O(N) as we have N recursive calls

For a bottom-up approach take a look at this StackOverflow accepted answer