Generate powerset in JS

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 ort

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.

StackExchange Code Review Q#139095, answer score: 7