As I was beefing up my past implementation of cartesianProductOf(), I decided to look into set theory a little bit more. After looking through some Wikipedia pages, I found another process that may be of interest to JavaScript programmers that have to deal with sets: a JavaScript implementation of finding a power set. Here is my code to do this:

function powerSetOf(arrFull) {
  var ret = [], fullLen = arrFull.length, last = fullLen - 1;
  function get(arrPrefix, start, lenToFind) {
    for(lenToFind--; start < fullLen; start++)
      if(!lenToFind)
        ret.push(arrPrefix.concat(&#91;arrFull&#91;start&#93;&#93;));
      else if(start < last)
        get(arrPrefix.concat(&#91;arrFull&#91;start&#93;&#93;), start + 1, lenToFind);
  }
  for(var lenToFind = fullLen; lenToFind > 0; lenToFind--)
    get([], 0, lenToFind);
  return ret.concat([[]]);
}

Although the above code works, I couldn’t help think that there was a simpler way of achieving the same goal. After fumbling around the idea in my head, I came up with the following, shorter solution:

function powerSetOf(arr) {
  var item, ret = [[]], max = arr.length - 1;
  function fn(arrPrefix, start) {
    for(; ret.push(item = arrPrefix.concat([arr[start]])) && start < max;)
      fn(item, ++start);
  }
  if(max + 1)
    fn(&#91;&#93;, 0);
  return ret;
}
&#91;/code&#93;

Unlike the first solution, the above one does not return the results ordered by size.  On the other hand, this solution is shorter, an works faster.

You may have noticed that neither solution removes duplicates if they exist within the array.  If you want to remove all duplicates from an array, you can make a build of <a href="http://jpaq.org/">jPaq</a> that has the <code>Array.prototype.uniquify()</code> function and then use it as follows:


// Your array of numbers or whatever.
var arr = [1,2,1,3,4,3,2];

// Get the power set for your array.
var arrPowerSet = powerSetOf(arr.uniquify());
Categories: BlogJavaScriptJScriptMath

1 Comment

ori · December 24, 2016 at 4:12 PM

Your power set implementation is amazing. good job!
Just realized I’m thanking you for something you did 5 years ago 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *