[R] Sorting vector based on pairs of comparisons

[Jim Lemon]

Hi Bert,
Good reference and David Urbina's example showed that a simple swap
was position dependent. The reason I pursued this is that it seems
more efficient to sequentially apply the precedence rules to the
arbitrarily sorted elements of the vector than to go through the
directed graph approach. By changing the simple position swap to an
insertion of the out-of-sequence element before its precedence pair,
both examples work correctly and adding precedence rules to the
initial list also produces a correct result. The output of the
examples below is a bit verbose, as I added a printout of the vector
at each step, ending with a logical indicating whether repos (element
reposition) was called.

repos<-function(x,i1,i2) {
 tmp<-x[i2]
 x<-x[-i2]
 if(i1 > 1) return(c(x[1:(i1-1)],tmp,x[i1:length(x)]))
 else return(c(tmp,x))
}
mpo<-function(x) {
 L<-unique(as.vector(x))
 for(i in 1:nrow(x)) {
  i1<-which(L==x[i,1])
  i2<-which(L==x[i,2])
  if(i2<i1) L<-repos(L,i1,i2)
  cat(L,i2<i1,"\n")
 }
 cat("\n")
 return(L)
}
# Pedro's example
Smaller<-c("ASD", "DFE", "ASD", "SDR", "EDF", "ASD")
Larger<-c("SDR", "EDF", "KLM", "KLM", "SDR", "EDF")
matComp<-cbind(Smaller,Larger)
mpo(matComp)
# David Urbina's example
priors<-c("A","B","C","C","D","E","E","F","G")
posts<-c("E","H","A","D","E","B","F","G","H")
dinnerMat<-cbind(priors,posts)
mpo(dinnerMat)
# add the condition that the taquitos must precede the guacamole
dinnerMat<-rbind(dinnerMat,c("G","B"))
mpo(dinnerMat)

To echo David Urbina's disclaimer, I would like to know if I have made
any mistakes.

Jim

> On 15/03/2019 08.53, Bert Gunter wrote:
> If I understand correctly, the answer is a topological sort.
>
> Here is an explanation
>
> https://davidurbina.blog/on-partial-order-total-order-and-the-topological-sort/
>
> This was found by a simple web search on
> "Convert partial ordering to total ordering"
> Btw.  Please use search engines before posting here.
>
> Bert