List all combinations of factors (interactions) with no observations in a dataframe, up to a given dimension, removing redundancies

Question

For a given dataframe with only factor columns, I want to list all combinations of factors for up to `m` attributes that do not appear in the data. Below is a simple example: ``` d <- expand.grid(w=factor(1:2), x=factor(1:2), y=factor(1:2), z=factor(1:2)) # These combinations are removed by tail(): rmcomb <- 5; head(d, rmcomb) ## w x y z ## 1 1 1 1 1 ## 2 2 1 1 1 ## 3 1 2 1 1 ## 4 2 2 1 1 ## 5 1 1 2 1 d <- tail(d, -rmcomb) ftable(d, row.vars=c("w", "x")) ## y 1 2 ## z 1 2 1 2 ## w x ## 1 1 0 1 0 1 ## 2 0 1 1 1 ## 2 1 0 1 1 1 ## 2 0 1 1 1 ``` For `m == 3`, we consider all 4 + 6 + 4 = 14 combinations of up to three attributes in `d`: ``` m <- 3 library(plyr) llply( 1:m, function(i) combn(ncol(d), i, simplify=F) ) -> cc unlist(cc, recursive=F) -> cc length(cc) ## [1] 14 ``` We can now tabulate selected columns of the data using `table`, and use `which` to find entries with zeros: ``` llply( cc, function(cols) { which(table(d[, cols]) == 0, arr.ind=T) -> z colnames(z) <- names(d)[cols] if…

Accepted Answer

Here's how you can continue your algo to pick out those sequences. First let's convert your list to a matrix, with NA's filled in. I find this easier to deal with, but I'm sure with some effort you can make it work with a list as well:

```
m = as.matrix(rbind.fill(lapply(zz, as.data.frame)))
#      y z  w  x
#[1,]  1 1 NA NA
#[2,] NA 1  1  1
#[3,]  1 1  1 NA
#[4,]  1 1  2 NA
#[5,]  1 1 NA  1
#[6,]  1 1 NA  2
```

Now let's introduce a function which will tell us if each row of a matrix given by `subseq` is a "subsequence" of `seq`, meaning it is already covered by `seq` as per OP's definitions:

```
is.subsequence = function(seq, subseq) {
  comp = seq == t(subseq)

rowSums(t(is.na(comp) == is.na(seq) &
            matrix(!(comp %in% FALSE), nrow = length(seq)))) == length(seq)
}
```

All that's left is to iterate over the matrix and throw out the covered sequences. We can do this going from top to bottom because of the automatic arrangement of `zz` from OP.

```
i = 1
while(i < nrow(m)) {
  m = rbind(m[1:i,], tail(m, -i)[!is.subsequence(m[i,], tail(m, -i)),])

i = i+1
}

m
#      y z  w  x
#[1,]  1 1 NA NA
#[2,] NA 1  1  1
```

And you can go back to a list if you like:

```
apply(m, 1, na.omit)
```

List all combinations of factors (interactions) with no observations in a dataframe, up to a given dimension, removing redundancies

Solution

Problem

Related problems