R, data.table: find all combinations of a list excluding each element paired with itself

Question

I would like to efficiently find all combinations of a list excluding the combination of each element to itself. For example, with a list of A,B,C,D find all combinations excluding A-A, B-B, C-C, D-D.

I can do this in what seems to be an inefficient way using this code:

x <- c("A","B","C","D")
dt <- CJ(x,x)
dt <- dt[!V1==V2]

The problem is that the third line takes as about 4 times as long to run as the second line. So for a large list like my real data, line 2 and line 3 together can take a very long time.

I am using data.table 1.9.6, R 3.2.2, and R Studio on Windows 7.

Thanks so much.

@Frank Thanks for pointing out that other post. I don't know how I missed it. It has some interesting approaches in it. — FG7, May 14 '16 at 10:37

Frank · Accepted Answer · 2016-05-13T19:49:42.050

Well, this is something of an improvement:

n = 1e4; x = seq(n)

# combn (variant of @Psidom's answer)
system.time({
  cn = transpose(combn(x, 2, simplify=FALSE))
  r  = rbind( setDT(cn), rev(cn) )
})
# takes forever, so i cut it off

# op's code
system.time({
  r0 = CJ(x,x)[V1 != V2]
})
#    user  system elapsed 
#    1.69    0.63    1.50 

# use indices in the final step
system.time({
  r1 = CJ(x,x)[-seq(1L, .N, by=length(x)+1L)]
})
#    user  system elapsed 
#    1.17    0.42    0.96

And some more:

# build it manually
system.time({
  xlen = length(x)
  r2 = data.table(rep(x, each = xlen), V2 = x)[-seq(1L, .N, by=xlen+1L)]
})
#    user  system elapsed 
#    3.03    0.60    2.79 

# ... or ...
system.time({
  xlen = length(x)
  r2 = data.table(rep(x, each = xlen-1L), rep.int(x, xlen)[-seq(1L, xlen^2, by=xlen+1L)])
})    
#    user  system elapsed 
#    2.79    0.25    3.07 

# build it manually special for the case of two cols
system.time({
  r3 = setDT(list(x))[, .(V2 = x), by=V1][ -seq(1L, .N, by=length(x)+1L) ]
})
#    user  system elapsed 
#    0.92    0.25    0.86 

# ... or ...
system.time({
  r4 = setDT(list(x))[, .(V2 = x[-.GRP]), by=V1]
})
#    user  system elapsed 
#    0.85    0.32    1.19

# verify
identical(r0, r1) # TRUE
identical(setkey(r0, NULL), r2) # TRUE
identical(setkey(r0, NULL), r3) # TRUE
identical(setkey(r0, NULL), r4) # TRUE

Maybe you can do a little better by writing your own CJ with Rcpp. It might also be worth noting that everything is faster with integers (instead of characters):

x = rep(LETTERS, 5e2)
system.time(CJ(x,x))
#    user  system elapsed 
#    7.06    1.81    6.61 


x = rep(1:26, 5e2)
system.time(CJ(x,x))
#    user  system elapsed 
#    3.39    0.88    2.95

So if x is a character vector, it might be best to use seq_along(x) for the combinatorial tasks and then map back to the character values like x[V1] afterwards.

@Psidom Thanks :) I like your answer and it was the first way I thought to approach it. Something must be miscoded in `combn` for it to be so slow, since this is precisely what it is built to do. — Frank, May 13 '16 at 19:14
No idea. `CJ()` is just so much faster than `combn()`. But `rbind()` is also a fault here since it is usually time consuming if the data table is large. — Psidom, May 13 '16 at 19:17
@Frank Your answer is great and gives lots of different options to work with. The benchmarking really helps. Thanks. — FG7, May 14 '16 at 10:40

R, data.table: find all combinations of a list excluding each element paired with itself

1 Answers1