Permutations with repetitions algorithm in R Given a string of length n, print all permutation of the given string.


The code bellow generates all permutations (with repetitions) for the given string and stores them in object res. Could you suggest ways to make the code faster (or a completely different algorithm written in R)? (For the "ABRACADABRA" word it takes more than 9 minutes to complete) 

#############################################################
word &lt;- "ABRACADABRA"
#############################################################

vec &lt;- unlist(strsplit(word,""))
charTable &lt;- sort(table(vec),decreasing = TRUE)
totChars  &lt;- sum(charTable)

combTable &lt;-choose(c(totChars,totChars-cumsum(charTable)),charTable)
combTable &lt;-combTable[combTable&gt;0]
names(combTable) &lt;- names(charTable)
totCombs &lt;- prod(combTable)

# initialize res
res &lt;- data.frame(matrix(rep(NA,totCombs*totChars),ncol=totChars))


for(i in 1:length(combTable)){
  totRows &lt;- prod(combTable[1:i])
  copyRows &lt;- prod(combTable[1:(i-1)])

  if (totRows&gt;copyRows){ 
    tmp &lt;- res[1:copyRows,]
    for(j in 1:(combTable[i]-1)){
      res[(j*copyRows+1):((j+1)*copyRows),] &lt;- tmp
    }
  }

  tmpCombs &lt;- t(combn(ifelse(i&gt;1,totChars-cumsum(charTable)[i-1],totChars), charTable[i]))
  letr &lt;- names(charTable)[i]

  if(i==1){
    for(k in 1:totRows){
      res[k,tmpCombs[k,]] &lt;- letr
    }
  } else if (i&gt;1 &amp; totRows==copyRows){
    for(k in 1:totRows){
      res[k,is.na(res[k,])][tmpCombs[1,]] &lt;- letr
    }
  } else{
    grpRows &lt;- prod(combTable[1:(i-1)])

    for(k in 1 : combTable[i]){ 
      for(m in ((k-1)*grpRows+1):((k)*grpRows)){ 
        res[m,is.na(res[m,])][tmpCombs[k,]] &lt;- letr
      }
    }
  }
}
This is one of many instances where people would be tempted to say, "see, loops in R are slow".  And my response is, "loops aren't that slow, but you can put slow code in loops."

There's no reason res needs to be a data.frame.  Leave it as a matrix and your code runs in under a second on my laptop.

# initialize res
res &lt;- matrix(rep(NA,totCombs*totChars),ncol=totChars)


The lesson here is:


  If you don't need the multi-typed columns of a data.frame, use a matrix.




You might look into factoradics as another possible algorithm. That would allow you to generate permutations in lexicographic order.