thr3ads.net - R help - [R] Sorting vector based on pairs of comparisons [Mar 2019]

If this information is useful, please help other people find it:
Share via:

Pedro Conte de Barros

2019-Mar-14 11:29 UTC

[R] Sorting vector based on pairs of comparisons

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

Richard M. Heiberger

2019-Mar-14 12:04 UTC

head link

[R] Sorting vector based on pairs of comparisons

Try this. Anything that appears only in Smaller is candidate for smallest.
Among those, order is arbitrary.

Anything that appears only in Larger is a candidate for largest. Among
those order is arbitrary.

Remove rows of matComp containing the already classified items.  Repeat
with the smaller set.

On Thu, Mar 14, 2019 at 07:30 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.
>
	[[alternative HTML version deleted]]

Bert Gunter

2019-Mar-14 13:09 UTC

head link

[R] Sorting vector based on pairs of comparisons

This cannot be done unless transitivity is guaranteed. Is it?

S   L

a  b
b  c
c  a

Bert


On Thu, Mar 14, 2019, 4:30 AM 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.
>
	[[alternative HTML version deleted]]

Pedro Conte de Barros

2019-Mar-14 14:14 UTC

head link

[R] Sorting vector based on pairs of comparisons

Thanks for this.

Yes, this is checked before trying to process this.

Pedro

On 14/03/2019 14.09, Bert Gunter wrote:
This cannot be done unless transitivity is guaranteed. Is it?

S   L

a  b
b  c
c  a

Bert


On Thu, Mar 14, 2019, 4:30 AM 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.

	[[alternative HTML version deleted]]

William Dunlap

2019-Mar-14 15:07 UTC

head link

[R] Sorting vector based on pairs of comparisons

This is called topological sorting in some circles.  The function below
will give you one ordering that is consistent with the contraints but not
all possible orderings.  I couldn't find such a function in core R so I
wrote one a while back based on Kahn's algorithm, as described in Wikipedia.
> Smaller <- c("ASD", "DFE", "ASD",
"SDR", "EDF", "ASD")
> Larger <- c("SDR", "EDF", "KLM",
"KLM", "SDR", "EDF")
> matComp <- cbind(Smaller, Larger)
> sortTopologically(matComp, unique(as.vector(matComp)))[1] "ASD" "DFE" "EDF" "SDR"
"KLM"

Bill Dunlap
TIBCO Software
wdunlap tibco.com

sortTopologically <- function(edgeMatrix, V)
{
    # edgeMatrix is 2-column matrix which describes a partial
    #   ordering of a set of vertices. The first column is the 'from'
vertex,
    #   the second the 'to' vertex.
    # V is the vector of all the vertices in the graph.
    #
    # Return a vector, L, consisting of the vertices in
    #   V in an order consistent with the partial ordering
    #   described by edgeMatrix.
    # Throw an error if such an ordering is not possible.
    #
    # Use Kahn's algorithm (
https://en.wikipedia.org/wiki/Topological_sorting).
    #
    # Note that disconnected vertices will not be mentioned in edgeMatrix,
    #   but will be in V.
    stopifnot(is.matrix(edgeMatrix),
              ncol(edgeMatrix)==2,
              !any(is.na(edgeMatrix)),
              !any(is.na(V)),
              all(as.vector(edgeMatrix) %in% V))
    L <- V[0] # match the type of the input
    S <- setdiff(V, edgeMatrix[, 2])
    V <- setdiff(V, S)
    while(length(S) > 0) {
        n <- S[1]
        # cat("Adding", n, "to L", "\n")
        L <- c(L, n)
        S <- S[-1]
        mRow <- edgeMatrix[,1] == n
        edgeMatrix <- edgeMatrix[ !mRow, , drop=FALSE ]
        S <- c(S, setdiff(V, edgeMatrix[,2]))
        V <- setdiff(V, S)
    }
    if (nrow(edgeMatrix) > 0) {
        stop("There are cycles in the dependency graph")
    }
    L
}


On Thu, Mar 14, 2019 at 4:30 AM 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.
>
	[[alternative HTML version deleted]]

Jim Lemon

2019-Mar-15 05:49 UTC

head link

[R] Sorting vector based on pairs of comparisons

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.

Bert Gunter

2019-Mar-15 07:53 UTC

head link

[R] Sorting vector based on pairs of comparisons

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]]

Marcelo Mariano Silva

2019-May-03 13:28 UTC

head link

[R] Loading EDF files

Dear All,

I have tried to load an EDF file using the code below and I received the
following massage :

Error in signals[[sn]]$signal[nextInCSignal[sn]:lastOne] <- samples[[sn]] :

replacement has length zero

What this massage means?
Is there any problem with the EDF file?

Code used:
hdr <-
readEdfHeader("/lasse/neurobit/edf/medidas/g1/G1medida1.edf");


df_id1 <- readEdfSignals(hdr, signals = "All", from = 0, till =
Inf,
physical = TRUE, fragments = TRUE, recordStarts = TRUE, mergeASignals TRUE,
simplify = TRUE);


Any help would be highly appreciated.


Mariano

>
>
	[[alternative HTML version deleted]]

Marcelo Mariano Silva

2019-May-03 13:31 UTC

head link

[R] Loading EDF files

Dear All,

I have tried to load an EDF file using the code below and I received the
following massage :

Error in signals[[sn]]$signal[nextInCSignal[sn]:lastOne] <- samples[[sn]] :

replacement has length zero

What this massage means?
Is there any problem with the EDF file?

Code used:
hdr <-
readEdfHeader("/lasse/neurobit/edf/medidas/g1/G1medida1.edf");


df_id1 <- readEdfSignals(hdr, signals = "All", from = 0, till =
Inf,
physical = TRUE, fragments = TRUE, recordStarts = TRUE, mergeASignals TRUE,
simplify = TRUE);


Any help would be highly appreciated.


Mariano

>
>
	[[alternative HTML version deleted]]

R help - Mar 2019 - Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Sorting vector based on pairs of comparisons

[R] Loading EDF files

[R] Loading EDF files