sorting problem

[Comp1597]

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]

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]

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]

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]

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

 

[Comp1597]

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
ordered? I can't find anything on the web about this, although I
would have thought it was a standard problem.

 

[Kai-Uwe Bux]

(e-mail address 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.

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

 

[Thomas Wintschel]

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

 

[James Kanze]

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".)

 

[Vladimir Jovic]

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)

 

[Comp1597]

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.

 

[Comp1597]

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


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.


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:[email protected]
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.

 

[Comp1597]

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).

 

[Comp1597]

(e-mail address 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.

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.

 

[Vladimir Jovic]

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

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

 

[Comp1597]

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.

 

[wij]

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?

 

[Comp1597]

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?"

 

[Carlo Milanesi]

(e-mail address removed) 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

 

[Kai-Uwe Bux]

(e-mail address 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.

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