Skip to content

Instantly share code, notes, and snippets.

@tantalor
Created June 3, 2012 03:02
Show Gist options
  • Save tantalor/2861511 to your computer and use it in GitHub Desktop.
Save tantalor/2861511 to your computer and use it in GitHub Desktop.
linear algorithm to generate catalan numbers
def catalan():
"""Yields catalan numbers: 1 1 2 5 14 42 132..."""
n = 0
c = 1
while 1:
yield c
n = n+1
c = c * 2 * (2*n-1) / (n+1)
# print the first ten catalan numbers
from itertools import islice
for n, c in enumerate(islice(catalan(), 10)):
print n, c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment