Tidbits @ Kassemi
A collection of opinions, thoughts, tricks and misc. information.Saturday, June 24, 2006
Farey Sequence Python Implementation
I looked this up a little earlier today, and wasn't finding anything that would give me a simple farey sequence with python. Figured I may as well post what I wrote that I'm about to stick up in the python cookbook.
def farey(n):
def gcd(a,b):
while b: a,b = b,a%b
return a
def simplify(a,b):
g = gcd(a,b)
return (a/g,b/g)
fs = dict()
for i in xrange(1,n+1):
for i2 in xrange(1,i+1):
if i2 < n and i != i2:
r = simplify(i2,i)
fs[float(i2)/i] = r
return [fs[k] for k in sorted(fs.keys())]
It neglects the (0,1) and (1,1) because they're obvious enough and I
end up removing them in my code anyway. Somebody out there can probably
figure out a more efficient and elegant solution, but this is pretty
quick and works just fine.
Take it easy,
James
def farey(n):
def gcd(a,b):
while b: a,b = b,a%b
return a
def simplify(a,b):
g = gcd(a,b)
return (a/g,b/g)
fs = dict()
for i in xrange(1,n+1):
for i2 in xrange(1,i+1):
if i2 < n and i != i2:
r = simplify(i2,i)
fs[float(i2)/i] = r
return [fs[k] for k in sorted(fs.keys())]
It neglects the (0,1) and (1,1) because they're obvious enough and I
end up removing them in my code anyway. Somebody out there can probably
figure out a more efficient and elegant solution, but this is pretty
quick and works just fine.
Take it easy,
James
Archives
August 2005 September 2005 October 2005 November 2005 December 2005 January 2006 February 2006 March 2006 April 2006 June 2006 July 2006 August 2006 September 2006 October 2006 November 2006
