sorting problem

Discussion in 'C++' started by Comp1597@yahoo.co.uk, Apr 2, 2009.

  1. Guest

    Suppose we have pairs of integers of the form (a,b). I want to define
    (a,b) <= (c,d) as meaning a >=c and b<=d
    (The motivation for this definition is that it means that the interval
    (a,b) is a subset of (c,d) ).

    Are there any STL functions that can be used for this type of sort? I
    don't believe the standard sort (applied to the standard containers)
    would work.

    Thank you.
     
    , Apr 2, 2009
    #1
    1. Advertising

  2. Guest

    On Apr 2, 1:10 am, wrote:
    > Suppose we have pairs of integers of the form (a,b).  I want to define
    > (a,b) <=  (c,d) as meaning   a >=c and b<=d
    > (The motivation for this definition is that it means that the interval
    > (a,b) is a subset of (c,d) ).
    >
    > Are there any STL functions that can be used for this type of sort?  I
    > don't believe the standard sort (applied to the standard containers)
    > would work.
    >
    > Thank you.


    I should have said explicitly that I want to sort according to this
    new definition of <=. Of course, there will be incomparable
    elements. My aim is to transform the original set of pairs into
    several sets of pairs where each set is totally ordered.
     
    , Apr 2, 2009
    #2
    1. Advertising

  3. wrote:
    > On Apr 2, 1:10 am, wrote:
    >> Suppose we have pairs of integers of the form (a,b). I want to define
    >> (a,b) <= (c,d) as meaning a >=c and b<=d
    >> (The motivation for this definition is that it means that the interval
    >> (a,b) is a subset of (c,d) ).
    >>
    >> Are there any STL functions that can be used for this type of sort? I
    >> don't believe the standard sort (applied to the standard containers)
    >> would work.
    >>
    >> Thank you.

    >
    > I should have said explicitly that I want to sort according to this
    > new definition of <=. Of course, there will be incomparable
    > elements. My aim is to transform the original set of pairs into
    > several sets of pairs where each set is totally ordered.


    Standard sort applies predicate but the predicate should have the strict
    weak ordering trait. I am not sure that the "less-or-equal" qualifies.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Apr 2, 2009
    #3
  4. Guest

    On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > wrote:
    > > On Apr 2, 1:10 am, wrote:
    > >> Suppose we have pairs of integers of the form (a,b).  I want to define
    > >> (a,b) <=  (c,d) as meaning   a >=c and b<=d
    > >> (The motivation for this definition is that it means that the interval
    > >> (a,b) is a subset of (c,d) ).

    >
    > >> Are there any STL functions that can be used for this type of sort?  I
    > >> don't believe the standard sort (applied to the standard containers)
    > >> would work.

    >
    > >> Thank you.

    >
    > > I should have said explicitly that I want to sort according to this
    > > new definition of <=.  Of course, there will be incomparable
    > > elements.  My aim is to transform the original set of pairs into
    > > several sets of pairs  where each set is totally ordered.

    >
    > Standard sort applies predicate but the predicate should have the strict
    > weak ordering trait.  I am not sure that the "less-or-equal" qualifies.
    >
    > V
    > --
    > Please remove capital 'A's when replying by e-mail
    > I do not respond to top-posted replies, please don't ask


    Yes, I've read that too. But unfortunately my sources are vague on
    what "strict weak ordering" means.
    Under my ordering, if P and Q are intervals such that neither P <= Q
    or Q <= P, it could still hold that P <=Z is true but Q <= Z is
    false. I think this property prevents the predicate being used in
    sort.
     
    , Apr 2, 2009
    #4
  5. wrote:
    > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    >> wrote:
    >>> On Apr 2, 1:10 am, wrote:
    >>>> Suppose we have pairs of integers of the form (a,b). I want to define
    >>>> (a,b) <= (c,d) as meaning a >=c and b<=d
    >>>> (The motivation for this definition is that it means that the interval
    >>>> (a,b) is a subset of (c,d) ).
    >>>> Are there any STL functions that can be used for this type of sort? I
    >>>> don't believe the standard sort (applied to the standard containers)
    >>>> would work.
    >>>> Thank you.
    >>> I should have said explicitly that I want to sort according to this
    >>> new definition of <=. Of course, there will be incomparable
    >>> elements. My aim is to transform the original set of pairs into
    >>> several sets of pairs where each set is totally ordered.

    >> Standard sort applies predicate but the predicate should have the strict
    >> weak ordering trait. I am not sure that the "less-or-equal" qualifies.
    >>
    >> V
    >> --
    >> Please remove capital 'A's when replying by e-mail
    >> I do not respond to top-posted replies, please don't ask

    >
    > Yes, I've read that too. But unfortunately my sources are vague on
    > what "strict weak ordering" means.
    > Under my ordering, if P and Q are intervals such that neither P <= Q
    > or Q <= P, it could still hold that P <=Z is true but Q <= Z is
    > false. I think this property prevents the predicate being used in
    > sort.


    Sources are vague? What sources are those? Ever tried Wikipedia.org?

    First and foremost, to be able to sort, pred(x,x) should return 'false'.
    If you write your predicate as "less than *or equal*", then this
    simple rule of 'pred(x,x)' to be true is not going to be satisfied.
    Then there is if pred(x,y) == true, then !pred(y,x) == true. Won't be
    satisfied with '<=' semantics.

    What you could do is to define the correct 'a < b' as the complete
    inclusion of 'a' range into the 'b' range. That way when you sort, all
    equivalent ranges will end up next to each other anyway.

    Try it. Define

    bool mypredicate(std::pair<int,int> const& p1,
    std::pair<int,int> const& p2)
    {
    // if 'p1' is a complete subrange of 'p2', return true
    // otherwise return false.
    }

    then sort an array (or a vector) of 'std::pair<int,int>' using std::sort
    and that predicate. See what happens. Experiment with overlapping
    ranges, equal ranges, fully enclosed ranges, etc. Mix them up, sort,
    print out the results. See if it fits what you expected. If not, post
    your code here, post your expectations, post the results, explain how
    it's not what you expected, and we'll be happy to help you.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Apr 2, 2009
    #5
  6. Guest

    On Apr 2, 1:56 am, Victor Bazarov <> wrote:
    > wrote:
    > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > >> wrote:
    > >>> On Apr 2, 1:10 am, wrote:
    > >>>> Suppose we have pairs of integers of the form (a,b).  I want to define
    > >>>> (a,b) <=  (c,d) as meaning   a >=c and b<=d
    > >>>> (The motivation for this definition is that it means that the interval
    > >>>> (a,b) is a subset of (c,d) ).
    > >>>> Are there any STL functions that can be used for this type of sort?  I
    > >>>> don't believe the standard sort (applied to the standard containers)
    > >>>> would work.
    > >>>> Thank you.
    > >>> I should have said explicitly that I want to sort according to this
    > >>> new definition of <=.  Of course, there will be incomparable
    > >>> elements.  My aim is to transform the original set of pairs into
    > >>> several sets of pairs  where each set is totally ordered.
    > >> Standard sort applies predicate but the predicate should have the strict
    > >> weak ordering trait.  I am not sure that the "less-or-equal" qualifies.

    >
    > >> V
    > >> --
    > >> Please remove capital 'A's when replying by e-mail
    > >> I do not respond to top-posted replies, please don't ask

    >
    > > Yes, I've read that too.  But unfortunately my sources are vague on
    > > what "strict weak ordering" means.
    > > Under my ordering,  if P and Q are intervals such that neither P <= Q
    > > or Q <= P, it could still hold that P <=Z is true but Q <= Z is
    > > false.  I think this property prevents the predicate being used in
    > > sort.

    >
    > Sources are vague?  What sources are those?  Ever tried Wikipedia.org?
    >
    > First and foremost, to be able to sort, pred(x,x) should return 'false'.
    >   If you write your predicate as "less than *or equal*", then this
    > simple rule of 'pred(x,x)' to be true is not going to be satisfied.
    > Then there is if pred(x,y) == true, then !pred(y,x) == true.  Won't be
    > satisfied with '<=' semantics.
    >
    > What you could do is to define the correct 'a < b' as the complete
    > inclusion of 'a' range into the 'b' range.  That way when you sort, all
    > equivalent ranges will end up next to each other anyway.
    >
    > Try it.  Define
    >
    >      bool mypredicate(std::pair<int,int> const& p1,
    >                       std::pair<int,int> const& p2)
    >      {
    >          // if 'p1' is a complete subrange of 'p2', return true
    >          // otherwise return false.
    >      }
    >
    > then sort an array (or a vector) of 'std::pair<int,int>' using std::sort
    > and that predicate.  See what happens.  Experiment with overlapping
    > ranges, equal ranges, fully enclosed ranges, etc.  Mix them up, sort,
    > print out the results.  See if it fits what you expected.  If not, post
    > your code here, post your expectations, post the results, explain how
    > it's not what you expected, and we'll be happy to help you.
    >
    > V
    > --
    > Please remove capital 'A's when replying by e-mail
    > I do not respond to top-posted replies, please don't ask


    Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
    included in [c,d] is not a strict weak ordering. Hence the predicate
    version of sort can't be applied. The reason it's not a strict weak
    ordering is that the relationship of incomparability is non-
    transitive.
    Hence my next question is: are there sorting algorithms in the STL
    that handle partially ordered sets which aren't strictly weakly
    ordered? I can't find anything on the web about this, although I
    would have thought it was a standard problem.
     
    , Apr 2, 2009
    #6
  7. Kai-Uwe Bux Guest

    wrote:

    [...]
    > Hence my next question is: are there sorting algorithms in the STL
    > that handle partially ordered sets which aren't strictly weakly
    > ordered?


    I don't think there is.

    > I can't find anything on the web about this, although I
    > would have thought it was a standard problem.


    E.g., a standard problem in this context is topological sorting: embed a
    partially ordered set into a totally ordered set so that the partial order
    is preserved. As far as I know, the standard library has no algorithm for
    that.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Apr 2, 2009
    #7
  8. wrote:
    > On Apr 2, 1:56 am, Victor Bazarov <> wrote:
    >> wrote:
    >>> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    >>>> wrote:
    >>>>> On Apr 2, 1:10 am, wrote:
    >>>>>> Suppose we have pairs of integers of the form (a,b). I want to
    >>>>>> define (a,b) <= (c,d) as meaning a >=c and b<=d
    >>>>>> (The motivation for this definition is that it means that the
    >>>>>> interval (a,b) is a subset of (c,d) ).
    >>>>>> Are there any STL functions that can be used for this type of
    >>>>>> sort? I don't believe the standard sort (applied to the standard
    >>>>>> containers) would work.
    >>>>>> Thank you.
    >>>>> I should have said explicitly that I want to sort according to
    >>>>> this new definition of <=. Of course, there will be incomparable
    >>>>> elements. My aim is to transform the original set of pairs into
    >>>>> several sets of pairs where each set is totally ordered.
    >>>> Standard sort applies predicate but the predicate should have the
    >>>> strict weak ordering trait. I am not sure that the "less-or-equal"
    >>>> qualifies.

    >>
    >>>> V
    >>>> --
    >>>> Please remove capital 'A's when replying by e-mail
    >>>> I do not respond to top-posted replies, please don't ask

    >>
    >>> Yes, I've read that too. But unfortunately my sources are vague on
    >>> what "strict weak ordering" means.
    >>> Under my ordering, if P and Q are intervals such that neither P <= Q
    >>> or Q <= P, it could still hold that P <=Z is true but Q <= Z is
    >>> false. I think this property prevents the predicate being used in
    >>> sort.

    >>
    >> Sources are vague? What sources are those? Ever tried Wikipedia.org?
    >>
    >> First and foremost, to be able to sort, pred(x,x) should return
    >> 'false'. If you write your predicate as "less than *or equal*", then
    >> this
    >> simple rule of 'pred(x,x)' to be true is not going to be satisfied.
    >> Then there is if pred(x,y) == true, then !pred(y,x) == true. Won't be
    >> satisfied with '<=' semantics.
    >>
    >> What you could do is to define the correct 'a < b' as the complete
    >> inclusion of 'a' range into the 'b' range. That way when you sort,
    >> all equivalent ranges will end up next to each other anyway.
    >>
    >> Try it. Define
    >>
    >> bool mypredicate(std::pair<int,int> const& p1,
    >> std::pair<int,int> const& p2)
    >> {
    >> // if 'p1' is a complete subrange of 'p2', return true
    >> // otherwise return false.
    >> }
    >>
    >> then sort an array (or a vector) of 'std::pair<int,int>' using
    >> std::sort and that predicate. See what happens. Experiment with
    >> overlapping ranges, equal ranges, fully enclosed ranges, etc. Mix
    >> them up, sort, print out the results. See if it fits what you
    >> expected. If not, post your code here, post your expectations, post
    >> the results, explain how it's not what you expected, and we'll be
    >> happy to help you.
    >>
    >> V
    >> --
    >> Please remove capital 'A's when replying by e-mail
    >> I do not respond to top-posted replies, please don't ask

    >
    > Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
    > included in [c,d] is not a strict weak ordering. Hence the predicate
    > version of sort can't be applied. The reason it's not a strict weak
    > ordering is that the relationship of incomparability is non-
    > transitive.
    > Hence my next question is: are there sorting algorithms in the STL
    > that handle partially ordered sets which aren't strictly weakly
    > ordered? I can't find anything on the web about this, although I
    > would have thought it was a standard problem.


    Into the land of ambiguity I tread once again...

    Short answer:
    a) STL sorting mechanisms allow for user defined predicates in situations such
    as this. This still requires the user to define the desired behaviour.
    b) When you say 'standard problem' - partial orderings do arise but the
    specifics of the elements being ordered and required levels of nesting (and, I
    am sure, other issues) have perhaps prevented generic algorithms from arising.

    For purposes of providing examples, look at set and multiset.

    Execute:
    set< int > bobo
    bobo.insert(1);
    bobo.insert(2);
    bobo.insert(2);
    bobo.insert(3);
    bobo contains three elements with values 1, 2 and 3.

    Execute:
    multiset< int > bobo
    bobo.insert(1);
    bobo.insert(2);
    bobo.insert(2);
    bobo.insert(3);
    bobo contains four elements with values 1, 2, 2 and 3.

    Both of these use the strict weak ordering. If a is NOT less than b and b is
    NOT less a then a == b. 'set' excludes multiples and 'multiset' allows them.
    The generic sorting routines require a predicate that makes this degree of
    distinction - it must be unambiguous so that the correct slot may be found.

    Given the following sets and the requirements you initially provided:

    A = [1, 5]
    B = [2, 4]
    C = [3, 5]
    D = [3, 4]

    B, C and D are all <= A
    D is <= B and C
    B is NOT <= C and C is NOT <= B

    so we get:

    D <= B ???? C <= A
    or
    D <= C ???? B <= A

    or some such thing.

    Defining '????' is specific to the problem at hand. Can you clarify?

    Tom
     
    Thomas Wintschel, Apr 2, 2009
    #8
  9. James Kanze Guest

    On Apr 2, 1:42 am, wrote:
    > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > > wrote:
    > > > On Apr 2, 1:10 am, wrote:
    > > >> Suppose we have pairs of integers of the form (a,b). I
    > > >> want to define (a,b) <= (c,d) as meaning a >=c and
    > > >> b<=d (The motivation for this definition is that it means
    > > >> that the interval (a,b) is a subset of (c,d) ).


    > > >> Are there any STL functions that can be used for this
    > > >> type of sort? I don't believe the standard sort (applied
    > > >> to the standard containers) would work.


    > > > I should have said explicitly that I want to sort
    > > > according to this new definition of <=. Of course, there
    > > > will be incomparable elements. My aim is to transform the
    > > > original set of pairs into several sets of pairs where
    > > > each set is totally ordered.


    > > Standard sort applies predicate but the predicate should
    > > have the strict weak ordering trait. I am not sure that the
    > > "less-or-equal" qualifies.


    The standard requires that pred(a,a) return false. This
    definitely means that pred can't be <=.

    > Yes, I've read that too. But unfortunately my sources are
    > vague on what "strict weak ordering" means.


    I'm not sure that it's an established concept, outside of the
    standard. But even if it is, it doesn't really matter---the
    standard explicitly defines what it means by the term, and when
    the standard explicitly defines a term, that's what it means in
    the standard, regardless of what it might mean elsewhere.
    Basically, for a binary predicate comp, if we define equiv(a,b)
    as !comp(a,b) && !comp(b,a), then both comp and equiv must be
    transitive.

    > Under my ordering, if P and Q are intervals such that neither
    > P <= Q or Q <= P, it could still hold that P <=Z is true but Q
    > <= Z is false. I think this property prevents the predicate
    > being used in sort.


    The fact that P <= Q and Q <= P are both true also prevents its
    use. (That's what the standard means by "strict".)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Apr 2, 2009
    #9
  10. wrote:
    > Suppose we have pairs of integers of the form (a,b). I want to define
    > (a,b) <= (c,d) as meaning a >=c and b<=d
    > (The motivation for this definition is that it means that the interval
    > (a,b) is a subset of (c,d) ).
    >
    > Are there any STL functions that can be used for this type of sort? I
    > don't believe the standard sort (applied to the standard containers)
    > would work.


    Why not use sort:
    http://www.cplusplus.com/reference/algorithm/sort.html
    ?
    Or sort_heap?

    (not sure whats difference between two)
     
    Vladimir Jovic, Apr 2, 2009
    #10
  11. Guest

    On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
    > wrote:
    > > Suppose we have pairs of integers of the form (a,b).  I want to define
    > > (a,b) <=  (c,d) as meaning   a >=c and b<=d
    > > (The motivation for this definition is that it means that the interval
    > > (a,b) is a subset of (c,d) ).

    >
    > > Are there any STL functions that can be used for this type of sort?  I
    > > don't believe the standard sort (applied to the standard containers)
    > > would work.

    >
    > Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
    > ?
    > Or sort_heap?
    >
    > (not sure whats difference between two)


    Can't use sort because it's not a strict weak ordering.
     
    , Apr 2, 2009
    #11
  12. Guest

    On Apr 2, 10:10 am, James Kanze <> wrote:
    > On Apr 2, 1:42 am, wrote:
    >
    >
    >
    > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > > > wrote:
    > > > > On Apr 2, 1:10 am, wrote:
    > > > >> Suppose we have pairs of integers of the form (a,b).  I
    > > > >> want to define (a,b) <=  (c,d) as meaning   a >=c and
    > > > >> b<=d (The motivation for this definition is that it means
    > > > >> that the interval (a,b) is a subset of (c,d) ).
    > > > >> Are there any STL functions that can be used for this
    > > > >> type of sort?  I don't believe the standard sort (applied
    > > > >> to the standard containers) would work.
    > > > > I should have said explicitly that I want to sort
    > > > > according to this new definition of <=.  Of course, there
    > > > > will be incomparable elements.  My aim is to transform the
    > > > > original set of pairs into several sets of pairs  where
    > > > > each set is totally ordered.
    > > > Standard sort applies predicate but the predicate should
    > > > have the strict weak ordering trait.  I am not sure that the
    > > > "less-or-equal" qualifies.

    >
    > The standard requires that pred(a,a) return false.  This
    > definitely means that pred can't be <=.
    >
    > > Yes, I've read that too.  But unfortunately my sources are
    > > vague on what "strict weak ordering" means.

    >
    > I'm not sure that it's an established concept, outside of the
    > standard.  But even if it is, it doesn't really matter---the
    > standard explicitly defines what it means by the term, and when
    > the standard explicitly defines a term, that's what it means in
    > the standard, regardless of what it might mean elsewhere.
    > Basically, for a binary predicate comp, if we define equiv(a,b)
    > as !comp(a,b) && !comp(b,a), then both comp and equiv must be
    > transitive.
    >
    > > Under my ordering,  if P and Q are intervals such that neither
    > > P <= Q or Q <= P, it could still hold that P <=Z is true but Q
    > > <= Z is false.  I think this property prevents the predicate
    > > being used in sort.

    >
    > The fact that P <= Q and Q <= P are both true also prevents its
    > use.  (That's what the standard means by "strict".)
    >
    > --
    > James Kanze (GABI Software)             email:
    > Conseils en informatique orientée objet/
    >                    Beratung in objektorientierter Datenverarbeitung
    > 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


    Thanks. My deeper problem is that if I define < on the pairs to mean
    (a,b) < (c,d) if the interval (a,b) is _strictly_ contained in (c,d).
    Then the relation is non-reflexive but is still not a strict weak
    ordering.
     
    , Apr 2, 2009
    #12
  13. Guest

    On Apr 2, 8:33 am, "Thomas Wintschel" <> wrote:
    > wrote:
    > > On Apr 2, 1:56 am, Victor Bazarov <> wrote:
    > >> wrote:
    > >>> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > >>>> wrote:
    > >>>>> On Apr 2, 1:10 am, wrote:
    > >>>>>> Suppose we have pairs of integers of the form (a,b). I want to
    > >>>>>> define (a,b) <= (c,d) as meaning a >=c and b<=d
    > >>>>>> (The motivation for this definition is that it means that the
    > >>>>>> interval (a,b) is a subset of (c,d) ).
    > >>>>>> Are there any STL functions that can be used for this type of
    > >>>>>> sort? I don't believe the standard sort (applied to the standard
    > >>>>>> containers) would work.
    > >>>>>> Thank you.
    > >>>>> I should have said explicitly that I want to sort according to
    > >>>>> this new definition of <=. Of course, there will be incomparable
    > >>>>> elements. My aim is to transform the original set of pairs into
    > >>>>> several sets of pairs where each set is totally ordered.
    > >>>> Standard sort applies predicate but the predicate should have the
    > >>>> strict weak ordering trait. I am not sure that the "less-or-equal"
    > >>>> qualifies.

    >
    > >>>> V
    > >>>> --
    > >>>> Please remove capital 'A's when replying by e-mail
    > >>>> I do not respond to top-posted replies, please don't ask

    >
    > >>> Yes, I've read that too. But unfortunately my sources are vague on
    > >>> what "strict weak ordering" means.
    > >>> Under my ordering, if P and Q are intervals such that neither P <= Q
    > >>> or Q <= P, it could still hold that P <=Z is true but Q <= Z is
    > >>> false. I think this property prevents the predicate being used in
    > >>> sort.

    >
    > >> Sources are vague? What sources are those? Ever tried Wikipedia.org?

    >
    > >> First and foremost, to be able to sort, pred(x,x) should return
    > >> 'false'. If you write your predicate as "less than *or equal*", then
    > >> this
    > >> simple rule of 'pred(x,x)' to be true is not going to be satisfied.
    > >> Then there is if pred(x,y) == true, then !pred(y,x) == true. Won't be
    > >> satisfied with '<=' semantics.

    >
    > >> What you could do is to define the correct 'a < b' as the complete
    > >> inclusion of 'a' range into the 'b' range. That way when you sort,
    > >> all equivalent ranges will end up next to each other anyway.

    >
    > >> Try it. Define

    >
    > >> bool mypredicate(std::pair<int,int> const& p1,
    > >> std::pair<int,int> const& p2)
    > >> {
    > >> // if 'p1' is a complete subrange of 'p2', return true
    > >> // otherwise return false.
    > >> }

    >
    > >> then sort an array (or a vector) of 'std::pair<int,int>' using
    > >> std::sort and that predicate. See what happens. Experiment with
    > >> overlapping ranges, equal ranges, fully enclosed ranges, etc. Mix
    > >> them up, sort, print out the results. See if it fits what you
    > >> expected. If not, post your code here, post your expectations, post
    > >> the results, explain how it's not what you expected, and we'll be
    > >> happy to help you.

    >
    > >> V
    > >> --
    > >> Please remove capital 'A's when replying by e-mail
    > >> I do not respond to top-posted replies, please don't ask

    >
    > > Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
    > > included in [c,d] is not a strict weak ordering.  Hence the predicate
    > > version of sort can't be applied.  The reason it's not a strict weak
    > > ordering is that the relationship of incomparability is non-
    > > transitive.
    > > Hence my next question is: are there sorting algorithms in the STL
    > > that handle partially ordered sets which aren't strictly weakly
    > > ordered?  I can't find anything on the web about this, although I
    > > would have thought it was a standard problem.

    >
    > Into the land of ambiguity I tread once again...
    >
    > Short answer:
    > a) STL sorting mechanisms allow for user defined predicates in situations such
    > as this.  This still requires the user to define the desired behaviour.
    > b) When you say 'standard problem' - partial orderings do arise but the
    > specifics of the elements being ordered and required levels of nesting (and, I
    > am sure, other issues) have perhaps prevented generic algorithms from arising.
    >
    > For purposes of providing examples, look at set and multiset.
    >
    > Execute:
    > set< int > bobo
    > bobo.insert(1);
    > bobo.insert(2);
    > bobo.insert(2);
    > bobo.insert(3);
    > bobo contains three elements with values 1, 2 and 3.
    >
    > Execute:
    > multiset< int > bobo
    > bobo.insert(1);
    > bobo.insert(2);
    > bobo.insert(2);
    > bobo.insert(3);
    > bobo contains four elements with values 1, 2, 2 and 3.
    >
    > Both of these use the strict weak ordering.  If a is NOT less than b and b is
    > NOT less a then a == b.  'set' excludes multiples and 'multiset' allows them.
    > The generic sorting routines require a predicate that makes this degree of
    > distinction - it must be unambiguous so that the correct slot may be found.
    >
    > Given the following sets and the requirements you initially provided:
    >
    > A = [1, 5]
    > B = [2, 4]
    > C = [3, 5]
    > D = [3, 4]
    >
    > B, C and D are all <= A
    > D is <= B and C
    > B is NOT <= C and C is NOT <= B
    >
    > so we get:
    >
    > D <= B ???? C <= A
    > or
    > D <= C ???? B <= A
    >
    > or some such thing.
    >
    > Defining '????' is specific to the problem at hand.  Can you clarify?
    >
    > Tom


    Thanks Tom,

    In the example you provide, I would like the result of the sort to be
    that B, C, and D are all <= A, D<= B, D <= C
    The result of the sort might be that B <= C or it might be that C <=
    B (I have no preference either way).
    In other words the sort preserves my relationship of <= but possibly
    adds new relations.
    The fact that such a <= exists mathematically speaking is a theorem
    known as the order-extension principle.

    But this all needs a correction. I should have said at the outset
    that the relation is < and it's defined by (a,b) < (c,d) if the
    interval (a,b) is strictly contained in (c,d) (it's non-reflexive in
    other words).

    Any idea how to get such a sort efficiently? Karl-Uwe Bux had the
    good suggestion of topological sorting but that's very slow in general
    -- order (n^2).
     
    , Apr 2, 2009
    #13
  14. Guest

    On Apr 2, 3:13 am, Kai-Uwe Bux <> wrote:
    > wrote:
    >
    > [...]
    >
    > > Hence my next question is: are there sorting algorithms in the STL
    > > that handle partially ordered sets which aren't strictly weakly
    > > ordered?  

    >
    > I don't think there is.
    >
    > > I can't find anything on the web about this, although I
    > > would have thought it was a standard problem.

    >
    > E.g., a standard problem in this context is topological sorting: embed a
    > partially ordered set into a totally ordered set so that the partial order
    > is preserved. As far as I know, the standard library has no algorithm for
    > that.
    >
    > Best
    >
    > Kai-Uwe Bux


    Thanks Kai-Uwe. I'm looking for something a bit faster than the
    topological sort algorithm which is order n^2.
    And please accept my apologies for referring to you as "Karl-Uwe"
    elsethread. My eyesight isn't great.
     
    , Apr 2, 2009
    #14
  15. wrote:
    > On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
    >> wrote:
    >>> Suppose we have pairs of integers of the form (a,b). I want to define
    >>> (a,b) <= (c,d) as meaning a >=c and b<=d
    >>> (The motivation for this definition is that it means that the interval
    >>> (a,b) is a subset of (c,d) ).
    >>> Are there any STL functions that can be used for this type of sort? I
    >>> don't believe the standard sort (applied to the standard containers)
    >>> would work.

    >> Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
    >> ?
    >> Or sort_heap?
    >>
    >> (not sure whats difference between two)

    >
    > Can't use sort because it's not a strict weak ordering.


    Why can't you use it with a custom function to compare?
     
    Vladimir Jovic, Apr 2, 2009
    #15
  16. Guest

    On Apr 2, 1:26 pm, Vladimir Jovic <> wrote:
    > wrote:
    > > On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
    > >> wrote:
    > >>> Suppose we have pairs of integers of the form (a,b).  I want to define
    > >>> (a,b) <=  (c,d) as meaning   a >=c and b<=d
    > >>> (The motivation for this definition is that it means that the interval
    > >>> (a,b) is a subset of (c,d) ).
    > >>> Are there any STL functions that can be used for this type of sort?  I
    > >>> don't believe the standard sort (applied to the standard containers)
    > >>> would work.
    > >> Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
    > >> ?
    > >> Or sort_heap?

    >
    > >> (not sure whats difference between two)

    >
    > > Can't use sort because it's not a strict weak ordering.

    >
    > Why can't you use it with a custom function to compare?


    Well, the link you posted stated that compare needs to be a strict
    weak ordering. My compare function < (strict set inclusion) is not a
    strict weak ordering. As Kai-Uwe pointed out, there is a topological
    sort algorithm to create a strict weak ordering from < but that is O
    (n^2) and I'm hoping for something faster.
     
    , Apr 2, 2009
    #16
  17. Guest

    On 4月2æ—¥, 下åˆ6時50分, wrote:
    > On Apr 2, 10:10 am, James Kanze <> wrote:
    >
    >
    >
    > > On Apr 2, 1:42 am, wrote:

    >
    > > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > > > > wrote:
    > > > > > On Apr 2, 1:10 am, wrote:
    > > > > >> Suppose we have pairs of integers of the form (a,b).  I
    > > > > >> want to define (a,b) <=  (c,d) as meaning   a >=c and
    > > > > >> b<=d (The motivation for this definition is that it means
    > > > > >> that the interval (a,b) is a subset of (c,d) ).
    > > > > >> Are there any STL functions that can be used for this
    > > > > >> type of sort?  I don't believe the standard sort (applied
    > > > > >> to the standard containers) would work.
    > > > > > I should have said explicitly that I want to sort
    > > > > > according to this new definition of <=.  Of course, there
    > > > > > will be incomparable elements.  My aim is to transform the
    > > > > > original set of pairs into several sets of pairs  where
    > > > > > each set is totally ordered.
    > > > > Standard sort applies predicate but the predicate should
    > > > > have the strict weak ordering trait.  I am not sure that the
    > > > > "less-or-equal" qualifies.

    >
    > > The standard requires that pred(a,a) return false.  This
    > > definitely means that pred can't be <=.

    >
    > > > Yes, I've read that too.  But unfortunately my sources are
    > > > vague on what "strict weak ordering" means.

    >
    > > I'm not sure that it's an established concept, outside of the
    > > standard.  But even if it is, it doesn't really matter---the
    > > standard explicitly defines what it means by the term, and when
    > > the standard explicitly defines a term, that's what it means in
    > > the standard, regardless of what it might mean elsewhere.
    > > Basically, for a binary predicate comp, if we define equiv(a,b)
    > > as !comp(a,b) && !comp(b,a), then both comp and equiv must be
    > > transitive.

    >
    > > > Under my ordering,  if P and Q are intervals such that neither
    > > > P <= Q or Q <= P, it could still hold that P <=Z is true but Q
    > > > <= Z is false.  I think this property prevents the predicate
    > > > being used in sort.

    >
    > > The fact that P <= Q and Q <= P are both true also prevents its
    > > use.  (That's what the standard means by "strict".)

    >
    > > --
    > > James Kanze (GABI Software)             email:
    > > Conseils en informatique orientée objet/
    > >                    Beratung in objektorientierter Datenverarbeitung
    > > 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

    >
    > Thanks.  My deeper problem is that if I define < on the pairs to mean
    > (a,b) < (c,d) if the interval (a,b) is _strictly_ contained in (c,d).
    > Then the relation is non-reflexive but is still not a strict weak
    > ordering.


    This is formal. Semantics is irrelevant.
    (a,b)<=(c,d) ==> !((a,b)>(c,d)) ==> !((c,d)<(a,b))

    < is implied by <= if ! is meaningful. Is that correct?
     
    , Apr 2, 2009
    #17
  18. Guest

    On Apr 2, 3:20 pm, wrote:
    > On 4月2æ—¥, 下åˆ6時50分, wrote:
    >
    >
    >
    > > On Apr 2, 10:10 am, James Kanze <> wrote:

    >
    > > > On Apr 2, 1:42 am, wrote:

    >
    > > > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
    > > > > > wrote:
    > > > > > > On Apr 2, 1:10 am, wrote:
    > > > > > >> Suppose we have pairs of integers of the form (a,b).  I
    > > > > > >> want to define (a,b) <=  (c,d) as meaning   a >=c and
    > > > > > >> b<=d (The motivation for this definition is that it means
    > > > > > >> that the interval (a,b) is a subset of (c,d) ).
    > > > > > >> Are there any STL functions that can be used for this
    > > > > > >> type of sort?  I don't believe the standard sort (applied
    > > > > > >> to the standard containers) would work.
    > > > > > > I should have said explicitly that I want to sort
    > > > > > > according to this new definition of <=.  Of course, there
    > > > > > > will be incomparable elements.  My aim is to transform the
    > > > > > > original set of pairs into several sets of pairs  where
    > > > > > > each set is totally ordered.
    > > > > > Standard sort applies predicate but the predicate should
    > > > > > have the strict weak ordering trait.  I am not sure that the
    > > > > > "less-or-equal" qualifies.

    >
    > > > The standard requires that pred(a,a) return false.  This
    > > > definitely means that pred can't be <=.

    >
    > > > > Yes, I've read that too.  But unfortunately my sources are
    > > > > vague on what "strict weak ordering" means.

    >
    > > > I'm not sure that it's an established concept, outside of the
    > > > standard.  But even if it is, it doesn't really matter---the
    > > > standard explicitly defines what it means by the term, and when
    > > > the standard explicitly defines a term, that's what it means in
    > > > the standard, regardless of what it might mean elsewhere.
    > > > Basically, for a binary predicate comp, if we define equiv(a,b)
    > > > as !comp(a,b) && !comp(b,a), then both comp and equiv must be
    > > > transitive.

    >
    > > > > Under my ordering,  if P and Q are intervals such that neither
    > > > > P <= Q or Q <= P, it could still hold that P <=Z is true but Q
    > > > > <= Z is false.  I think this property prevents the predicate
    > > > > being used in sort.

    >
    > > > The fact that P <= Q and Q <= P are both true also prevents its
    > > > use.  (That's what the standard means by "strict".)

    >
    > > > --
    > > > James Kanze (GABI Software)             email:
    > > > Conseils en informatique orientée objet/
    > > >                    Beratung in objektorientierter Datenverarbeitung
    > > > 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

    >
    > > Thanks.  My deeper problem is that if I define < on the pairs to mean
    > > (a,b) < (c,d) if the interval (a,b) is _strictly_ contained in (c,d).
    > > Then the relation is non-reflexive but is still not a strict weak
    > > ordering.

    >
    > This is formal. Semantics is irrelevant.
    >  (a,b)<=(c,d) ==> !((a,b)>(c,d)) ==> !((c,d)<(a,b))
    >
    > < is implied by <= if ! is meaningful. Is that correct?


    There are two problems that have been brought up by other posters -- a
    shallow problem and a deep problem.
    There is a shallow problem (the difference between <= and <) that's
    easy to work around.
    However, there's a deep problem: Even if you make the trivial change
    to use the < form of my predicate, you still don't get a strict weak
    ordering.
    As Kai-Uwe pointed out, the problem that set inclusion is not a strict
    weak ordering is a real obstacle and that's why Kai-Uwe suggested a
    topological-sort. However topological-sorting is very slow.

    I'm not sure what you mean by "that" when you ask "Is that correct?"
    I suspect that if I knew what you meant by "that", my answer would be
    "No, that is not correct?"
     
    , Apr 2, 2009
    #18
  19. ha scritto:
    > Suppose we have pairs of integers of the form (a,b). I want to define
    > (a,b) <= (c,d) as meaning a >=c and b<=d
    > (The motivation for this definition is that it means that the interval
    > (a,b) is a subset of (c,d) ).
    >
    > Are there any STL functions that can be used for this type of sort? I
    > don't believe the standard sort (applied to the standard containers)
    > would work.


    You may be interested in this research paper:
    http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf

    --

    Carlo Milanesi
    http://digilander.libero.it/carlmila
     
    Carlo Milanesi, Apr 2, 2009
    #19
  20. Kai-Uwe Bux Guest

    wrote:

    > On Apr 2, 3:13 am, Kai-Uwe Bux <> wrote:
    >> wrote:
    >>
    >> [...]
    >>
    >> > Hence my next question is: are there sorting algorithms in the STL
    >> > that handle partially ordered sets which aren't strictly weakly
    >> > ordered?

    >>
    >> I don't think there is.
    >>
    >> > I can't find anything on the web about this, although I
    >> > would have thought it was a standard problem.

    >>
    >> E.g., a standard problem in this context is topological sorting: embed a
    >> partially ordered set into a totally ordered set so that the partial
    >> order is preserved. As far as I know, the standard library has no
    >> algorithm for that.

    [...]
    > Thanks Kai-Uwe. I'm looking for something a bit faster than the
    > topological sort algorithm which is order n^2.


    You are searching for an efficient solution. That is commendable. However,
    it would be good if we knew what the problem is. From postings elsethread,
    I figured that you want to somehow sort intervals according to inclusion.
    But that is an ill-defined problem. What does count as sorted? And _why_ do
    you want to sort the intervals? Is it to speed up searching for an interval
    containing a given point? In that case, maybe it's easier to solve the
    underlying problem. Can you clarify?


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Apr 3, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hajime Kusakabe

    DataGrid - sorting/paging problem

    Hajime Kusakabe, Jul 30, 2003, in forum: ASP .Net
    Replies:
    2
    Views:
    503
    Saravana
    Jul 31, 2003
  2. Replies:
    2
    Views:
    1,491
    James Kanze
    Jul 6, 2010
  3. Jason
    Replies:
    0
    Views:
    412
    Jason
    Oct 4, 2006
  4. Tom Kirchner

    sorting by multiple criterias (sub-sorting)

    Tom Kirchner, Oct 11, 2003, in forum: Perl Misc
    Replies:
    3
    Views:
    514
    Michael Budash
    Oct 11, 2003
  5. Íéêüëáïò Êïýñáò

    Sorting a set works, sorting a dictionary fails ?

    Íéêüëáïò Êïýñáò, Jun 10, 2013, in forum: Python
    Replies:
    12
    Views:
    171
    Ulrich Eckhardt
    Jun 10, 2013
Loading...

Share This Page