Tag Archives: Math

Power Set

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([arrFull[start]]));
      else if(start < last)
        get(arrPrefix.concat([arrFull[start]]), 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([], 0);
  return ret;
}

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 jPaq that has the Array.prototype.uniquify() 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());

Cartesian Product of Multiple Arrays

A few weeks ago, I came across a question about finding the cartesian product of two or more arrays in JavaScript. For anybody who is looking to do so, I posted the following code on stackoverflow:

function cartesianProductOf() {
  return Array.prototype.reduce.call(arguments, function(a, b) {
    var ret = [];
    a.forEach(function(a) {
      b.forEach(function(b) {
        ret.push(a.concat([b]));
      });
    });
    return ret;
  }, [[]]);
}

It is important to note that the above code will only work on newer browsers that implement Array.prototype.forEach() and Array.prototype.reduce(). If you must allow this function to be used on any browser or even in a stand-alone Windows Host Script, I would suggest using this version of jPaq which implements the functions if they aren’t already present. As of yet, I have not received any requests to see this in a JavaScript library. If you do want it in a library, let me know of your suggestions for a better name than cartesianProductOf. My issue with the name is that it is too long.