3 ms·
The Wilf-Calkin tree also does that: http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree I refer to it
by ColinWright 14y ago
The Wilf-Calkin tree also does that:
http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree
I refer to it as Wilf-Calkin because that's how Neil Calkin refers to it, despite the alphabetical ordering on the Wikipedia page.
Even better, there's an explicit formula for generating rationals, without repeats:
http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadth_first_traversal http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadt...
- Jtsummers 14y agoNeat, that was in a tab I hadn't reached yet. Though for the purposes of this sort of search, the Stern-Brocot tree has the nice property of being a binary search tree. Allowing you to constrain the breadth as well as the depth of the search.