[R] Sorting vector based on pairs of comparisons

[Pedro Conte de Barros]

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 using gmail.com<mailto:drjimlemon using 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 using ualg.pt<mailto:pbarros using 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 using r-project.org<mailto:R-help using 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 using r-project.org<mailto:R-help using 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]]