Union/Intersect two continuous sets

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Union/Intersect two continuous sets

谢一鸣
Dear All,

It is my first time using this mail list to post a question. And I
sincerely hope that this will not bother any subscribers.
So far as I know, there are functions like union( ), which can help to
combine two sets of discrete data. But what if the data sets are with
continuous data. For instance, I got three sets like [2, 4], [5, 6], [3.4,
5.5]. I wonder if there is a quick solution to recognize their union is [2,
6], and return the size of this union 6-2=4 to me. The similar demand is
for the intersection operation.
If you get any idea, please inform me. Thanks in advance!

Xie

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
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.
Reply | Threaded
Open this post in threaded view
|

Re: Union/Intersect two continuous sets

Hans W Borchers
谢一鸣 <cutexym <at> gmail.com> writes:

> Dear All,
>
> It is my first time using this mail list to post a question. And I
> sincerely hope that this will not bother any subscribers.
> So far as I know, there are functions like union( ), which can help to
> combine two sets of discrete data. But what if the data sets are with
> continuous data. For instance, I got three sets like [2, 4], [5, 6], [3.4,
> 5.5]. I wonder if there is a quick solution to recognize their union is [2,
> 6], and return the size of this union 6-2=4 to me. The similar demand is
> for the intersection operation.
> If you get any idea, please inform me. Thanks in advance!
>
> Xie

I got interested in your request as I could use it myself (not for intervals,
but a similar kind of problem).
I assume, you represent your set of intervals as a matrix M with two columns,
first column the left endpoints, second the right ones.

Intersection is easy, as it is the interval from the maximum of left end
points to the minimum of the right end points (or NULL if the maximum is
greater than the minimum).

For the union I didn't see a simple, i.e. one or two lines, solution ahead,
so here is my dumb, looped version. Surely there are more elegant solutions
coming.

    # Mnew the union of intervals in M, an (nx2)-matrix with n > 1:
    o <- order(M[, 1], M[, 2])
    L <- M[o, 1]; R <- M[o, 2]
    k <- 1
    Mnew <- matrix(c(L[k], R[k]), 1, 2)
    for (i in 2:nrow(M)) {
        if (L[i] <= Mnew[k, 2]) {
            Mnew[k, 2] <- max(R[i], Mnew[k, 2])
        } else {
            k <- k+1
            Mnew <- rbind(Mnew, c(L[i], R[i]))
        }
    }

    # Inew the intersection of intervals in M, an (nx2)-matrix with n > 1:
    L <- max(M[, 1]); R <- min(M[, 2])
    Inew <- if (L <= R) c(L, R) else c()

______________________________________________
[hidden email] mailing list
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.
Reply | Threaded
Open this post in threaded view
|

Re: Union/Intersect two continuous sets

William Dunlap
Late last month Hans Borchers suggested the following
solution (which I trivially converted to a function):

u0 <- function(M)
{
    # Mnew the union of intervals in M, an (nx2)-matrix with n > 1:
    o <- order(M[, 1], M[, 2])
    L <- M[o, 1]; R <- M[o, 2]
    k <- 1
    Mnew <- matrix(c(L[k], R[k]), 1, 2)
    for (i in 2:nrow(M)) {
        if (L[i] <= Mnew[k, 2]) {
            Mnew[k, 2] <- max(R[i], Mnew[k, 2])
        } else {
            k <- k+1
            Mnew <- rbind(Mnew, c(L[i], R[i]))
        }
    }
    Mnew
}

I believe the following does the same thing.  It
is quicker.  It may easily be changed to give you
the intervals where p or more of the input intervals
overlap instead of the current 1 or more.

u1 <- function(M)
{
    o <- order(c(M[, 1], M[, 2]))
    n <- cumsum( rep(c(1, -1), each=nrow(M))[o])
    startPos <- c(TRUE, n[-1]==1 & n[-length(n)]==0)
    endPos <- c(FALSE, n[-1]==0 & n[-length(n)]==1)
    M <- M[o]
    cbind(M[startPos], M[endPos])
}

Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com

> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Hans W Borchers
> Sent: Thursday, December 22, 2011 7:50 AM
> To: [hidden email]
> Subject: Re: [R] Union/Intersect two continuous sets
>
> 谢一鸣 <cutexym <at> gmail.com> writes:
>
> > Dear All,
> >
> > It is my first time using this mail list to post a question. And I
> > sincerely hope that this will not bother any subscribers.
> > So far as I know, there are functions like union( ), which can help to
> > combine two sets of discrete data. But what if the data sets are with
> > continuous data. For instance, I got three sets like [2, 4], [5, 6], [3.4,
> > 5.5]. I wonder if there is a quick solution to recognize their union is [2,
> > 6], and return the size of this union 6-2=4 to me. The similar demand is
> > for the intersection operation.
> > If you get any idea, please inform me. Thanks in advance!
> >
> > Xie
>
> I got interested in your request as I could use it myself (not for intervals,
> but a similar kind of problem).
> I assume, you represent your set of intervals as a matrix M with two columns,
> first column the left endpoints, second the right ones.
>
> Intersection is easy, as it is the interval from the maximum of left end
> points to the minimum of the right end points (or NULL if the maximum is
> greater than the minimum).
>
> For the union I didn't see a simple, i.e. one or two lines, solution ahead,
> so here is my dumb, looped version. Surely there are more elegant solutions
> coming.
>
>     # Mnew the union of intervals in M, an (nx2)-matrix with n > 1:
>     o <- order(M[, 1], M[, 2])
>     L <- M[o, 1]; R <- M[o, 2]
>     k <- 1
>     Mnew <- matrix(c(L[k], R[k]), 1, 2)
>     for (i in 2:nrow(M)) {
>         if (L[i] <= Mnew[k, 2]) {
>             Mnew[k, 2] <- max(R[i], Mnew[k, 2])
>         } else {
>             k <- k+1
>             Mnew <- rbind(Mnew, c(L[i], R[i]))
>         }
>     }
>
>     # Inew the intersection of intervals in M, an (nx2)-matrix with n > 1:
>     L <- max(M[, 1]); R <- min(M[, 2])
>     Inew <- if (L <= R) c(L, R) else c()
>
> ______________________________________________
> [hidden email] mailing list
> 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.
______________________________________________
[hidden email] mailing list
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.