Elements of Programming Chapter 4 “Linear orderings”

This entry is part of a series, Elements of Programming»

Chapter 4 describes binary relations. The main concepts are equality, ordering and stability. A relation is defined as a predicate taking two parameters of the same type and written as $r(a,b)$ . A relation is:

transitive iff $r(a,b)$ and $r(b,c)$ implies $r(a,c)$
strict iff it never holds between and element and itself
reflexive iff it always holds between and element and itself
symmetric iff the relation between elements $a$ and $b$ implies that the relation holds between $b$ and $a$
asymmetric iff the relation between elements $a$ and $b$ implies that the relation does not hold between $b$ and $a$
an equivalence if it is transitive, reflexive and symmetric

Given a relation $r$ we can define

the complement relation between $a$ and $b$ as $neg r(a,b)$
the converse relation between $a$ and $b$ as $r(b,a)$
the complement_of_converse relation between $a$ and $b$ as $neg r(b,a)$

Given an equivalence relation we can define equivalence classes as $[a]_r=$ { $b;r(a,b)$ }. Equality of $r$ guarantees that $[a]_r = [b]_r$ if and only if $r(a,b)$ . Key function is a function $f$ such that $f(a) = f(b)$ iff $r(a,b)$ .

A relation is a total ordering if it is transitive and obeys the trichotomy law: for any two elements $a$ and $b$ exactly one of the following holds:

$r(a,b)$ ,
$r(b,a)$ ,
$a=b$

A weak ordering is defined as a transitive relation, such that there exists equivalence relation $e$ on the same domain and for any two elements $a$ and $b$ from its domain exactly one of the following holds:

$r(a,b)$
$r(b,a)$
$e(a,b)$

The symmetric complement of a relation $r$ is defined as $neg r(a,b) land neg r(b,a)$ .

Given a weak ordering $r$ and and sequence of objects we can ask which of them is minimal, maximal, second minimal, second maximal, and so on. If we define minimal as an element $a$ such that $r(b,a)$ does not hold for any $b$ , then it is possible that we’ll end up with many minimal elements. To have a definition that picks only one minimal element, we choose the one that comes first in our sequence. More formally, instead of the original relation $r$ , we provide a new relation $hat{r}$ :

$hat{r}(a_i, a_j) iff r(a_i, a_j) lor (neg r(a_i, b_j) land i < j)$

where $i$ and $j$ represent the position (or stability index) of $a_i$ and $a_j$ , respectively, in the original sequence. The relation $hat{r}$ now uniquely identifies a minimal element.

An algorithm is stable if it maintains the original ordering of equivalent objects.

Chapter 4 then discusses order-selection algorithms that return the $j$ -th greatest element from a $k$ -elements sequence. The complexity of those algorithms grows very fast with $k$ . This problem has been addressed by reduction to a constrained subproblem, in which we assume that some elements are ordered. For example, function select_1_4_ab() returns the minimal element out of four under assumption that the first and second are in order. It works fine up to 5 elements, after which a new problem emerges: a subprocedure related to the constrained subproblem is called with non-ordered arguments which causes stability problem. The systematic approach is to pass stability indices along with parameters.

For an abstract species there can be a natural total ordering representing its fundamental operations, denoted by $<$ . For some species, additional relationships can hold, e.g. for integers $a < rm{successor}(a)$ , $a < b implies rm{successor}(a) < rm{successor}(b)$ , and so on. For some species there is no natural total ordering. To enable logarithmic search on such species, we have to provide some total ordering. An example is a lexicographical ordering for complex numbers.

Some procedures have a natural relationship. An example is $a < b iff b > a$ . We say they come in clusters.

Chapter 4 ends with a discussion of potential extensions to order selection procedures.

returning a reference instead of a copy, which enables the result of select_X_Y() to be on the left side of an assignment.
order selection that assumes a total ordering and therefore does not have to check the stability index
the use of a three-valued comparison (lesser, equal, greater) which could save an extra procedure call

Entries in this series:

Posted Friday, October 29th, 2010 under Chapter Summary, EoP Study Group.

Pavel Holoborodko says:

February 22, 2011 at 12:35 am

Hi, guys!

My comment is not C++ related, sorry.

I am author of QuickLaTeX plugin for WordPress which you are using to render LaTeX equations on the site.

I’ve just noticed that “Posting/Commenting” page (“LaTeX formulas” paragraph) says the site is based on different LaTeX plugin – WP-LaTeX. I think it is misleading for visitors.

Could you consider fixing it? Thank you in advance.

Quote

Dave Abrahams says:

February 23, 2011 at 11:00 pm

Yoiks! Sorry for that; I forgot to update that page when your wonderful plugin solved the vertical alignment problem that WP-LaTeX has. Thanks for pointing that out to us. Credit where it is due, and all that.

Dave AbrahamsQuote
- Pavel Holoborodko says:
  
  February 24, 2011 at 4:39 am
  I appreciate your support. Thank you.
  
  Also I want to thank you for all the efforts towards Boost creation and development – I use it in my projects. I have your book on template metaprogramming – it is very insightful, it showed me several beautiful techniques I had no idea about.
  
  There is one question I have about open source C++ libraries. Maybe it is not appropriate place to ask but I am sure you have the answer – so I’ll risk.
  
  Projects I work on are mostly science-related involving complex numerical algorithms, heavy computations, simulations, etc.
  
  I love C++ for the high performance and sufficient abstraction from low-level tasks.
  
  However I frequently see lack of C++ libraries for the math. Even basics, like multi-precision floating point calculations, big integer numbers, complex numbers (with arbitrary precision). I do not even raise question about decent numerical methods library, symbolic computations, plotting, …
  
  All we have in C++ is very fragmented pieces of required bunch of libraries, e.g. linear algebra is well covered, but numerical optimization, signal processing are not covered at all.
  
  Besides existing C++ math libraries are very provider-dependent, with different design techniques and incompatibilities with each other.
  
  In connection with all of this what do you think of idea to create (unified) scientific library for C++? Like SciPy/NumPy in Python world?
  
  Of cause such development costs money and time. I have no idea how to fund this work and share results as open source in the same time. Do you think it is possible at all? It seems you find the solution with Boost.Pro.
  
  First step would be to create arbitrary precision basic numerical types, e.g. mpreal, mpint, mpcomplex and then use them as a basement.
  
  I develop MPFR C++ interface for the famous floating-point multiprecision library – MPFR. It encapsulates low-level C stuff in mpreal class easy-to-use instead of built-in C++ types. It is drop in the sea, but even this bit of work is readily accepted by C++ science community.
  
  I want to develop such type of libraries further but it is near-impossible if this work does not bring funding to itself.
  
  So my questions can be summarized as:
  - what is the place of science-libraries in C++/Boost roadmap.
  - how to develop open source C++ libraries which funds itself (probably very stupid question, but I hope for some pointers to read at least).
  Thank you and sorry for long post.
  Pavel HoloborodkoQuote
  - Dave Abrahams says:
    
    March 7, 2011 at 10:13 am
    
    Hi Pavel,
    
    Sorry it took me so long to notice your posting. I sympathize with your sense that there are not enough math libraries for C++. In fact, despite the success of Boost, I think there are still simply not enough good C++ libraries out there, regardless of domain. What I don’t see clearly is how establishing a “unified” library would help to produce the commitment and funding you point out would be necessary.
    
    As to the C++/Boost roadmap, I’m afraid there isn’t one. All we have are a bunch of people, each contributing his or her piece to the puzzle. It’s virtually impossible to plan the future content of Boost.
    
    How to develop self-funding open-source C++ libraries? Hmm, great question! I wish I knew. BoostPro is very lucky when a client comes along who wants us to just write open-source libraries (for one example, see this posting from my personal blog). I would love it if all our work could be of that nature, but that’s not the way things have turned out for us.
    
    Dave AbrahamsQuote
    - joel falcou says:
      
      March 7, 2011 at 3:16 pm
      
      chiming in adn givign my own 2cts.
      
      This is a very difficult endeavor. As I often say, such library is rather hard to design due to all orthogonal needs users may express and all low level details you need to care about. This lead me and a couple of coworker to start such effort while keeping in mind extensibility (see http://github.com/MetaScale/nt2). The library to fit every need in SciComp is not possible, better bank on interoperable, generic component for computation built on generic wrappers on top of architectural encapsulation.
      
      As for your question: 1/ I wish there were more effort on this. we currently plan to start submitting sub-component of our own scientific computing library as boost component. I know Dave appreciated what we presented last year and this year, we’ll try to get the first part of it reviewed and submitted. Now, should we got a Boost.Numeric or more focused libraries that can interact, I don’t really know.
      
      2/ good question, in our case we decided to go down the road of building a start-up and having side products built on top of our open source effort to fund people working on both the OS and non-OS components. I wish to be able to come back here in one year and tell you about our success
      
      joel falcouQuote

Petar Marendic says:

October 30, 2010 at 9:43 pm

There’s an error in the post: “A relation is total if it obeys the trichotomy law.”

Actually, a a binary relation R over a set X is total if for all a and b in X, a is related to b or b is related to a (or both) [courtesy of Wikipedia].

The exact wording in the text deals only with a special kind of relation, an order relation, and goes like this: “A relation is a total ordering if it is transitive and obeys the trichotomy law, … “

Anyhow, a nice chapter though as I noted in my solutions to the exercises the authors could have devoted a few sentences to explaining why they chose to depart from the standard mathematical definition of a total order relation.

Piotr Jachowicz says:

October 31, 2010 at 4:17 am

I’ve fixed this paragraph, thanks!

BTW definition of weak_ordering changed in 1st printing is incorrect. It has been and changed in 2nd+ printings (see errata http://www.elementsofprogramming.com/eop-errata.pdf)

Piotr JachowiczQuote

C++Next

Elements of Programming Chapter 4 “Linear orderings”

7 Responses to “Elements of Programming Chapter 4 “Linear orderings””

Leave a Comment (post replies using links below individual comments)