Velocity Reviews > C++ > sorting problem

# sorting problem

Comp1597@yahoo.co.uk
Guest
Posts: n/a

 04-01-2009
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.

Comp1597@yahoo.co.uk
Guest
Posts: n/a

 04-01-2009
On Apr 2, 1:10*am, (E-Mail Removed) 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.

Victor Bazarov
Guest
Posts: n/a

 04-01-2009
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> On Apr 2, 1:10 am, (E-Mail Removed) 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
--

Comp1597@yahoo.co.uk
Guest
Posts: n/a

 04-01-2009
On Apr 2, 1:35*am, Victor Bazarov <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > On Apr 2, 1:10 am, (E-Mail Removed) 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
> --

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.

Victor Bazarov
Guest
Posts: n/a

 04-01-2009
(E-Mail Removed) wrote:
> On Apr 2, 1:35 am, Victor Bazarov <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>> On Apr 2, 1:10 am, (E-Mail Removed) 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
>> --

>
> 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:air<int,int> const& p1,
std:air<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:air<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
it's not what you expected, and we'll be happy to help you.

V
--

Comp1597@yahoo.co.uk
Guest
Posts: n/a

 04-02-2009
On Apr 2, 1:56*am, Victor Bazarov <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > On Apr 2, 1:35 am, Victor Bazarov <(E-Mail Removed)> wrote:
> >> (E-Mail Removed) wrote:
> >>> On Apr 2, 1:10 am, (E-Mail Removed) 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
> >> --
> >> 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:air<int,int> const& p1,
> * * * * * * * * * * * std:air<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:air<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
> --

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
would have thought it was a standard problem.

Kai-Uwe Bux
Guest
Posts: n/a

 04-02-2009
(E-Mail Removed) 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.

> 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

Thomas Wintschel
Guest
Posts: n/a

 04-02-2009
(E-Mail Removed) wrote:
> On Apr 2, 1:56 am, Victor Bazarov <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>> On Apr 2, 1:35 am, Victor Bazarov <(E-Mail Removed)> wrote:
>>>> (E-Mail Removed) wrote:
>>>>> On Apr 2, 1:10 am, (E-Mail Removed) 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
>>>> --

>>
>>> 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:air<int,int> const& p1,
>> std:air<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:air<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
>>
>> V
>> --

>
> 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
> would have thought it was a standard problem.

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

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

James Kanze
Guest
Posts: n/a

 04-02-2009
On Apr 2, 1:42 am, (E-Mail Removed) wrote:
> On Apr 2, 1:35 am, Victor Bazarov <(E-Mail Removed)> wrote:
> > (E-Mail Removed) wrote:
> > > On Apr 2, 1:10 am, (E-Mail Removed) 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:(E-Mail Removed)
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

Guest
Posts: n/a

 04-02-2009
(E-Mail Removed) 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)