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 On Thu, Mar 14, 2019, 10:50 PM Jim Lemon <drjimlemon at gmail.com> wrote:> Hi Pedro, > This looks too simple to me, but it seems to work: > > swap<-function(x,i1,i2) { > tmp<-x[i1] > x[i1]<-x[i2] > x[i2]<-tmp > return(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<-swap(L,i1,i2) > } > return(L) > } > mpo(matComp) > > Jim > > On Thu, Mar 14, 2019 at 10:30 PM Pedro Conte de Barros <pbarros at ualg.pt> > wrote: > > > > Dear All, > > > > This should be a quite established algorithm, but I have been searching > > for a couple days already without finding any satisfactory solution. > > > > I have a matrix defining pairs of Smaller-Larger arbitrary character > > values, like below > > > > Smaller <- c("ASD", "DFE", "ASD", "SDR", "EDF", "ASD") > > > > Larger <- c("SDR", "EDF", "KLM", "KLM", "SDR", "EDF" > > > > matComp <- cbind(Smaller, Larger) > > > > so that matComp looks like this > > > > Smaller Larger > > [1,] "ASD" "SDR" > > [2,] "DFE" "EDF" > > [3,] "ASD" "KLM" > > [4,] "SDR" "KLM" > > [5,] "EDF" "SDR" > > [6,] "ASD" "EDF" > > > > This matrix establishes six pairs of "larger than" relationships that > > can be used to sort the unique values in the matrix, > > > > > unique(as.vector(matComp)) > > [1] "ASD" "DFE" "SDR" "EDF" "KLM" > > > > Specifically, I would like to get this: > > > > sorted <- c("ASD", "DFE", "EDF", "SDR", "KLM") > > > > or, equally valid (my matrix does not have the full information): > > > > sorted <- c("DFE", "ASD", "EDF", "SDR", "KLM") > > > > Preferably, I would get the different combinations of the unique values > > that satisfy the "larger than" conditions in the matrix... > > > > > > I am sure this is a trivial problem, but I could not find any algorithm > > to solve it. > > > > Any help would be highly appreciated > > > > ______________________________________________ > > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > > https://stat.ethz.ch/mailman/listinfo/r-help > > PLEASE do read the posting guide > http://www.R-project.org/posting-guide.html > > and provide commented, minimal, self-contained, reproducible code. > > ______________________________________________ > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide > http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >[[alternative HTML version deleted]]
Pedro Conte de Barros
2019-Mar-15 08:46 UTC
[R] Sorting vector based on pairs of comparisons
Thanks Bert. Excellent reference, I learned a lot from it! Just a note: I did use search engines for at least 2 days before posting. BUT as often happens, I did not use the right keywords. I tried several variants of "Convert ordered pairs to sorted", "Sort vector on paired comparisons" and about anything else I could think of round "paired comparisons". But the problem was, I did not know what was the correct terminology to use for this search, that was why I had to ask. This is where humans excel versus computer search engines - find things based on imprecise specifications- and thanks again for pointing me in the right direction. Best, Pedro 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 On Thu, Mar 14, 2019, 10:50 PM Jim Lemon <drjimlemon at gmail.com<mailto:drjimlemon at gmail.com>> wrote: Hi Pedro, This looks too simple to me, but it seems to work: swap<-function(x,i1,i2) { tmp<-x[i1] x[i1]<-x[i2] x[i2]<-tmp return(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<-swap(L,i1,i2) } return(L) } mpo(matComp) Jim On Thu, Mar 14, 2019 at 10:30 PM Pedro Conte de Barros <pbarros at ualg.pt<mailto:pbarros at ualg.pt>> wrote:> > Dear All, > > This should be a quite established algorithm, but I have been searching > for a couple days already without finding any satisfactory solution. > > I have a matrix defining pairs of Smaller-Larger arbitrary character > values, like below > > Smaller <- c("ASD", "DFE", "ASD", "SDR", "EDF", "ASD") > > Larger <- c("SDR", "EDF", "KLM", "KLM", "SDR", "EDF" > > matComp <- cbind(Smaller, Larger) > > so that matComp looks like this > > Smaller Larger > [1,] "ASD" "SDR" > [2,] "DFE" "EDF" > [3,] "ASD" "KLM" > [4,] "SDR" "KLM" > [5,] "EDF" "SDR" > [6,] "ASD" "EDF" > > This matrix establishes six pairs of "larger than" relationships that > can be used to sort the unique values in the matrix, > > > unique(as.vector(matComp)) > [1] "ASD" "DFE" "SDR" "EDF" "KLM" > > Specifically, I would like to get this: > > sorted <- c("ASD", "DFE", "EDF", "SDR", "KLM") > > or, equally valid (my matrix does not have the full information): > > sorted <- c("DFE", "ASD", "EDF", "SDR", "KLM") > > Preferably, I would get the different combinations of the unique values > that satisfy the "larger than" conditions in the matrix... > > > I am sure this is a trivial problem, but I could not find any algorithm > to solve it. > > Any help would be highly appreciated > > ______________________________________________ > R-help at r-project.org<mailto:R-help at r-project.org> mailing list -- To UNSUBSCRIBE and more, see > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code.______________________________________________ R-help at r-project.org<mailto:R-help at r-project.org> mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. [[alternative HTML version deleted]]
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