On 4 May 2007 07:21:49 -0700, Thomas Nelson <[EMAIL PROTECTED]> wrote: > I want to generate all the fractions between 1 and limit (with > limit>1) in an orderly fashion, without duplicates.
Might I suggest the Stern-Brocot tree (http://en.wikipedia.org/wiki/Stern-Brocot_tree) It will eliminate the need for sets as the algorithm gurantees: "Every positive rational number can be found in this tree exactly once and in lowest terms". The order will be different than your algorithm, though. #An overly simplified fraction class for this example: class Fraction: def __init__ (self, num, den): self.num = num self.den = den def __repr__ (self): return '%(num)d/%(den)d' % self.__dict__ def all_ratios(limit): seq = [Fraction(1,1), Fraction(limit,1)] while True: newseq = seq[:1] pairs = [seq[x:x+2] for x in range(len(seq)-1)] for pair in pairs: #find the mediant value between each pair in the series newval = Fraction(pair[0].num+pair[1].num, pair[0].den+pair[1].den) yield newval newseq.append(newval) newseq.append(pair[1]) seq = newseq -Dave -- http://mail.python.org/mailman/listinfo/python-list
