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 <- "ABRACADABRA"
#############################################################
vec <- unlist(strsplit(word,""))
charTable <- sort(table(vec),decreasing = TRUE)
totChars <- sum(charTable)
combTable <-choose(c(totChars,totChars-cumsum(charTable)),charTable)
combTable <-combTable[combTable>0]
names(combTable) <- names(charTable)
totCombs <- prod(combTable)
# initialize res
res <- data.frame(matrix(rep(NA,totCombs*totChars),ncol=totChars))
for(i in 1:length(combTable)){
totRows <- prod(combTable[1:i])
copyRows <- prod(combTable[1:(i-1)])
if (totRows>copyRows){
tmp <- res[1:copyRows,]
for(j in 1:(combTable[i]-1)){
res[(j*copyRows+1):((j+1)*copyRows),] <- tmp
}
}
tmpCombs <- t(combn(ifelse(i>1,totChars-cumsum(charTable)[i-1],totChars), charTable[i]))
letr <- names(charTable)[i]
if(i==1){
for(k in 1:totRows){
res[k,tmpCombs[k,]] <- letr
}
} else if (i>1 & totRows==copyRows){
for(k in 1:totRows){
res[k,is.na(res[k,])][tmpCombs[1,]] <- letr
}
} else{
grpRows <- 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,]] <- letr
}
}
}
}