October 4, 2012

Generating a powerset in ColdFusion

I recently needed to generate a powerset (a set of all subsets) of 3 HTML select boxes. The idea was that a user could choose 1-many options from each box, and they had to choose a value from all 3 boxes (none could be empty).

Select #1 had 4 values
Select #2 had 7 values
Select #3 had 13 values

Now, I needed to generate every possible permutation for these 3 select boxes based on the rules I defined above. That meant the possible number of combinations for each box was:

Select #1 had 16* possible combinations
Select #2 had 128* possible combinations
Select #3 had 8192* possible combinations

* It was actually 1 less than that, because a powerset take into consideration an empty selection, so in reality the numbers would have been 15, 127 and 8191.

This was calculated using 2n, where n is an number (integer) of options in a set, so 24, 27 and 213

Now, how did I go about calculating these powersets? I cheated :smile:

I grabbed a JavaScript function from Rosetta Code and ported it to ColdFusion.

Here is the function to generate a powerset from a set (array) of data:

public array function calculate(required array data)
  var ps = [""];
  var d = arguments.data;
  var lenData = arrayLen(d);
  var lenPS = 0;
  for (var i=1; i LTE lenData; i++)
    lenPS = arrayLen(ps);
    for (var j = 1; j LTE lenPS; j++)
      arrayAppend(ps, listAppend(ps[j], d[i]));
  return ps;

A sample powerset of 4 values (in this case 1,2,3,4) would be:

var Powerset = new Powerset();
var res = Powerset.calculate([1,2,3,4]);


By the way, my total combination across all 3 sets was a mere 16,777,216.

Grab from github if you prefer the CFC

© Michael Sharman 2017