2013/02/06

Set operations on more than two sets in R

Problem

Set operations are a common place thing to do in R, and the enabling functions in the base stats package are:

  • intersect(x, y)
  • union(x, y)
  • setdiff(x, y)
  • setequal(x, y)
That said, you'll note that each ONLY takes two arguments - i.e. set X and set Y - which was a limitation I needed to overcome recently.

Googling around I found that you can apply set operations to multiple (>2) sets using the Reduce() function.  For example, an intersection of sets stored in the list x would be achieved with:
Reduce(intersect, x)

However, things get trickier if you want to do a setdiff() in this manner - that is find the elements that are only in set a, but not in sets b, c, d, ..., etc.  Since I'm not a master at set theory, I decided to write my own, brute force method to get intersections, unions, and setdiffs for an arbitrary number of sets.

Implementation

The function I wrote uses a truth table to do this where:

  • rows are the union of all elements in all sets
  • columns are sets
So each "cell" of the table is TRUE if the element represented by the row is in the set represented by the column.

To find an element that intersects all sets, the values across the row need to be all TRUE.
To find an element that is only in one set, only one row value is TRUE.  To determine which set that element is in, numeric values are applied to each column such that:

  • col1 = 1
  • col2 = 2
  • col3 = 4
  • col4 = 8
  • ... and so on
The values above are multiplied by each row's TRUE/FALSE (ergo: 1/0) values and summed across to produce a row's inclusion value.

For example, if an element is only in set 2 (that is column 2) the corresponding row inclusion value is 2.  If an element is in both sets 2 and 3 (columns 2 and 3) the corresponding row inclusion value is 6.

Visually ...



124
set:xyzinc.val
aTFF1
bFTT6
cTFT5
dTTT7


Thus, determining intersections or setdiffs becomes a simple matter of filtering by row sums.



Code