Download code

Jump to: navigation, search

Back to Generating_all_rationals_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

allrats.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Generating_all_rationals_(Python)?oldid=19136
14 
15 def gcd(a,b):
16         """ the euclidean algorithm """
17         while a:
18                 a, b = b%a, a
19         return b
20 def generate_rationals():
21     """ generates each rational once, coded in a tuple: (i,j) = i/j"""
22     yield (0,1)
23     n = 0
24     while True:
25         for m in xrange(n):
26 	    (i,j) = (m+1,n-m)
27 	    if gcd(i,j) == 1:
28 	        yield (i,j)
29 	        yield (-i,j)
30         n += 1
31 
32 if __name__ == "__main__":
33         for (i,j) in generate_rationals():
34                 print "%d/%d" % (i,j)


hijacker
hijacker
hijacker
hijacker