R find all possible unique combinations

4
votes

I am trying to find all possible unique combinations in R. It seems that there have been a lot of similar questions asked, but I was not able to find the same one.

My question is to find combinations of m number of elements from vector x, but m could be larger than x. For example, pick 3 elements from letters[1:2], which hopefully can return:

combn(letters[1:2],3)
       [,1]  [,2]  [,3]  [,4] 
[1,]   "a"   "a"   "a"    "b"
[2,]   "a"   "a"   "b"    "b"
[3,]   "a"   "b"   "b"    "b"

But instead error in combn function n < m. There are similar functions including gtools:permutations, expand.grid.

Apologize again if someone asked the same questions previously, but I did not catch it. Thanks.

2
rcombinationscombn
what do you mean a combination of a,a,a what kind of combination is that? - Onyambu
I mean possibilities combining the elements in the vector source. - Jian
So how do you call it a unique combination while you are not ccombining it to anything? but rather repeating it? - Onyambu
The uniqueness is to say, for instance, aab, aba, baa are the same. - Jian
I think you are after the multichoose combinations. It looks like the itertools can help you with it's np_ or nc_ multiset functions - Gregor Thomas

2 Answers

5
votes

There are a few packages specifically built for this. The basic premise is that we need combinations with repetition of length m where m could be larger than the input vector. We start with the classic gtools:

library(gtools)
combinations(2, 3, letters[1:2], repeats.allowed = TRUE)
    [,1] [,2] [,3]
[1,] "a"  "a"  "a" 
[2,] "a"  "a"  "b" 
[3,] "a"  "b"  "b" 
[4,] "b"  "b"  "b"

And then there is arrangements which is a replacement for iterpc (the package linked by @Gregor in the comments above):

library(arrangements)
arrangements::combinations(2, 3, letters[1:2], replace = TRUE)
     [,1] [,2] [,3]
[1,] "a"  "a"  "a" 
[2,] "a"  "a"  "b" 
[3,] "a"  "b"  "b" 
[4,] "b"  "b"  "b"

And finally there is RcppAlgos, which I authored:

library(RcppAlgos)
comboGeneral(letters[1:2], 3, TRUE)
     [,1] [,2] [,3]
[1,] "a"  "a"  "a" 
[2,] "a"  "a"  "b" 
[3,] "a"  "b"  "b" 
[4,] "b"  "b"  "b"

combn is an awesome function that ships as one of the base packages with R, however one of its shortcomings is that it doesn't allow repetition (which is what is required here). I wrote a pretty comprehensive overview for problems exactly like this one that can be found here: A Walk Through a Slice of Combinatorics in R.

1
votes
combn1=function(x,m){
  n=ifelse(length(x)==1,ifelse(is.numeric(x),x,1),length(x))
  if(n>=m) return(combn(x,m))
  a=do.call(expand.grid, rep(list(x),m))
  b=t(unique(t(apply(a,1,sort))))
  `dimnames<-`(b,NULL)
}

combn1(letters[1],3)
     [,1]
[1,] "a" 
[2,] "a" 
[3,] "a" 
> combn1(letters[1:2],3)
     [,1] [,2] [,3] [,4]
[1,] "a"  "a"  "a"  "b" 
[2,] "a"  "a"  "b"  "b" 
[3,] "a"  "b"  "b"  "b" 
> combn1(letters[1:3],3)
     [,1]
[1,] "a" 
[2,] "b" 
[3,] "c"