James Tauber : Enumerating the Rationals in Python

James Saiz

journeyman of some

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.

This page last modified Tuesday 08 February, 2005
Content made available under a Creative Commons Attribution-NonCommercial-ShareAlike license