Enumerating the Rationals in Python


I've written a short script that enumerates the positive rationals without duplicates:

The script involves a simple generator wrapping a single-line iterative expression.

I've long been aware of the method of enumerating the positive rationals by walking the diagonals of the infinite matrix (with the numerator increasing across columns and denominator increasing down rows) but this results in duplicates (an infinite number for each rational number, in fact).

The approach taken in my script is based, instead, on walking a Calkin-Wilf tree. I became aware of this approach from a recent paper by Jeremy Gibbons, David Lester and Richard Bird which I found out about from the Lambda the Ultimate blog.

The original post was in the categories: python mathematics but I'm still in the process of migrating categories over.