rxk011 rxk011 - 4 days ago 4
R Question

Generate all possible permutations of incomplete distinct objects in R

Suppose

v=c(-1,-1,-1,0,0,0,1,1,1)
and I want to generate all the permutations. There are
9!/(3!3!3!)=1680


Currently, I'm using the following line to get that, but it is not very efficient.

unique(replicate(100000, sample(v), simplify=FALSE))


This is one possible case. I want to generalize this. Suppose
n
objects consist of
k
distinct objects
a1,a2,...,ak
with repetition numbers
n1,n2,...,nk (n1+n2+...+nk=n)
respectivly. Then
n!/(n1!n2!...nk!)


How do I do this efficiently?

Answer

One approach is to use a permutations function to generate all possibilities then filter. If you need a guarantee of all possibilities this has advantages over the sample method in your question however it can 'crash' if you have a long vector.

v=c(-1,-1,-1,0,0,0,1,1,1)
unique(combinat::permn(v))

This method is much less quick than @sirallen's approach. A generalization of that approach might be:

u  <- unique(v)
Pv <- expand.grid(rep(list(u),length(v)))
for(i in seq_along(u)) {
Pv <- Pv[rowSums(Pv==u[i])==sum(u[i]==v),]
}
dim(Pv)
Comments