**Fabio Marroni's Blog » R**, and kindly contributed to R-bloggers)

You might ask what R has to do with theater.

I assure you it has. I act in the theater group ‘ndescenze. We will soon present (actually, we just performed) a show based on the Marx Brothers Radio Shows. We shuffle actors and characters during the show (we like it complicated!) and we needed to find at least one sequence of scenes which allowed people to change dress and be ready quickly to be back on stage.

I manually described a number of rules based on the roles of the actors.

For example, “Teatro”, in which I act as Ravelli and I am on stage until the end of the scene, cannot be followed by “Autobus”, in which I act as Miss Dimple and I am on stage in the beginning of the scene…

After doing that, I just needed to find the combination of six scenes (named “affitto”,”autobus”,”eredita”,”ristorante”,”tassista” and “teatro”) which didn’t break any of the imposed rules.

No need to say that I used R! It worked, I found a good answer, but with a really ugly piece of code… Let’s see if you can find the right answer(s) and with a better piece of code (ok, the latter is not so difficult)

Here I list the rules:

“teatro” must take place after “affitto”, because in “affitto” we explain some things that will be needed for “teatro”.

They don’t need to be consecutive, though.

Then a list of consecutive combinations that are forbidden

“affitto” cannot be followed by “tassista” nor by “teatro”

“autobus” cannot be followed by “ristorante”

“eredita” cannot be followed by “tassista” nor by “autobus”

“ristorante” cannot be followed by “affitto”, “tassista”, “teatro” nor by “autobus”

“tassista” cannot be followed by “affitto”, “teatro” nor by “eredita”

“teatro” cannot be followed by “autobus”, “affitto”, nor by “ristorante”

Here’s the code:

scenes<-c("affitto","autobus","eredita","ristorante","tassista","teatro") choose.me<-expand.grid(list(scenes,scenes,scenes,scenes,scenes,scenes), stringsAsFactors=FALSE) for (bbb in 1: nrow(choose.me)) { if(length(unique(as.character(choose.me[bbb,])))<6) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="affitto") > which(choose.me[bbb,]=="teatro")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="affitto")+1==which(choose.me[bbb,]=="tassista")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="affitto")+1==which(choose.me[bbb,]=="teatro")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="autobus")+1==which(choose.me[bbb,]=="ristorante")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="eredita")+1==which(choose.me[bbb,]=="tassista")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="eredita")+1==which(choose.me[bbb,]=="autobus")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="ristorante")+1==which(choose.me[bbb,]=="affitto")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="ristorante")+1==which(choose.me[bbb,]=="tassista")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="ristorante")+1==which(choose.me[bbb,]=="teatro")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="ristorante")+1==which(choose.me[bbb,]=="autobus")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="tassista")+1==which(choose.me[bbb,]=="affitto")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="tassista")+1==which(choose.me[bbb,]=="teatro")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="tassista")+1==which(choose.me[bbb,]=="eredita")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="teatro")+1==which(choose.me[bbb,]=="autobus")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="teatro")+1==which(choose.me[bbb,]=="affitto")) {choose.me[bbb,]<-rep(NA,6);next} if(which(choose.me[bbb,]=="teatro")+1==which(choose.me[bbb,]=="ristorante")) {choose.me[bbb,]<-rep(NA,6);next} } choose.me<-na.omit(choose.me)

Using this code, I was able to find 10 combinations of scenes that were technically feasible. Among them we chose the one likely to have the best impact on the audience…

The list of all the technically possible scenes and the chosen one will be out soon… Obviously, if you attended our show you already know!

Waiting for comments on how to improve the code and your guesses for the right answer!

**Improved code by Paul Fruin**

Following Paul’s comment I paste below the complete code for solving the same problem. I tested it and it provides the right answer. In addition, Paul’s code avoids the loop and thus saves a considerable amount of time! I am always happy when I learn a way to avid a loop, so thanks Paul!

BTW: stay tuned, I will soon add alternative versions suggested by comments… I just need some time to test them and comment them!!

Here’s Paul’s code:

scenes<-c("affitto","autobus","eredita","ristorante","tassista","teatro") choose.me<-expand.grid(list(scenes,scenes,scenes,scenes,scenes,scenes), stringsAsFactors=FALSE) ##now knock out rows step by step, using apply() to index the bad rows choose.me[ apply(choose.me,1,function(x) ! length(unique(as.character(x)))<6),] -> choose.me #remove rows based on next criteria choose.me[ apply(choose.me,1,function(x) ! which(x=="affitto") > which(x=="teatro") ) , ] -> choose.me #remove al the other rows... choose.me[ apply(choose.me,1,function(x) ! which(x=="affitto")+1 == which(x=="tassista") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="affitto")+1 == which(x=="teatro") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="autobus")+1 == which(x=="ristorante") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="eredita")+1 == which(x=="tassista") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="eredita")+1 == which(x=="autobus") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="ristorante")+1 == which(x=="affitto") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="ristorante")+1 == which(x=="tassista") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="ristorante")+1 == which(x=="teatro") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="ristorante")+1 == which(x=="autobus") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="tassista")+1 == which(x=="affitto") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="tassista")+1 == which(x=="teatro") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="tassista")+1 == which(x=="eredita") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="teatro")+1 == which(x=="autobus") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="teatro")+1 == which(x=="affitto") ) , ] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="teatro")+1 == which(x=="ristorante") ) , ] -> choose.me

**Carlos Ortega** provided an even faster solution. It uses libraries “combinat” and “stringr” and it runs in less than 3 secs even on my old laptop! I tested it and it provides the right answer. I promise that I will try to learn this efficient implementation!

You can find Carlo’s code below:

a<-Sys.time() library(combinat) library(stringr) scenes<-c("affitto","autobus","eredita","ristorante","tassista","teatro") all.sce<-permn(scenes ) foo<-function(x) { str_c(x, collapse="-") } sce.god<-lapply(all.sce, foo) # Working data.frame sce.end<-as.data.frame(sce.god) names(sce.end)<-NULL sce.wrk<-t(sce.end) ###### Forbidden Rules r01<-c('affitto-tassista') r02<-c('affitto-teatro') r03<-c('autobus-ristorante') r04<-c('eredita-tassista') r05<-c('eredita-autobus') r06<-c('ristorante-affitto') r07<-c('ristorante-tassista') r08<-c('ristorante-teatro') r09<-c('ristorante-autobus') r10<-c('tassista-affitto') r11<-c('tassista-teatro') r12<-c('tassista-eredita') r13<-c('teatro-autobus') r14<-c('teatro-affitto') r15<-c('teatro-ristorante') r16<-c('^teatro') rul.for<-data.frame( r01, r02, r03, r04, r05, r06, r07, r08, r09, r10, r11, r12, r13, r14, r15, r16 ) ############# Process to get the valid scenes sce.ini<-sce.wrk for(i in 1:ncol(rul.for)) { rul.tmp<-as.vector(rul.for[1,i]) val.tmp<-str_locate(sce.ini, rul.tmp) sce.tmp<-sce.ini[is.na(val.tmp[,1])] sce.ini<-sce.tmp } ### To eliminate first rule Ð teatro after affittoÉ te.val<-str_locate(sce.ini, "teatro") af.val<-str_locate(sce.ini, "affitto") te.af<-data.frame(te=te.val[,1],af=af.val[,1]) no.val<-as.numeric(row.names(te.af[te.af$te < te.af$af,])) ### Valid Scenes valid.scenes <- sce.ini[-no.val] valid.scenes b<-Sys.time() b-a

Last but not least, **Ben Bolker** found another elegant solution providing the correct answer.

I paste it below:

scenes<-c("affitto","autobus","eredita","ristorante","tassista","teatro") choose.me<-expand.grid(list(scenes,scenes,scenes,scenes,scenes,scenes), stringsAsFactors=FALSE) ##now knock out rows step by step, using apply() to index the bad rows choose.me[ apply(choose.me,1,function(x) ! length(unique(as.character(x)))<6),] -> choose.me choose.me[ apply(choose.me,1,function(x) ! which(x=="affitto") > which(x=="teatro") ) , ] -> choose.me ##remove rows based on next criteria not_adjacent <- function(t1,t2) { apply(choose.me,1,function(x) ! (which(x==t1)+1 == which(x==t2))) } omit_pairs <- matrix(c("affitto","tassista", "affitto","teatro", "autobus","ristorante", "eredita","tassista", "eredita","autobus", "ristorante","affitto", "ristorante","tassista", "ristorante","teatro", "ristorante","autobus", "tassista","affitto", "tassista","teatro", "tassista","eredita", "teatro","autobus", "teatro","affitto", "teatro","ristorante"), ncol=2,byrow=TRUE) invisible(apply(omit_pairs,1, function(z) { choose.me <<- choose.me[not_adjacent(z[1],z[2]),] })) nrow(choose.me) ## 10

All the solutions provided so far were correct, fast and elegant. This makes me realize the paucity of my R skills, but at the same time stimulates me to learn more!

**leave a comment**for the author, please follow the link and comment on his blog:

**Fabio Marroni's Blog » R**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...