[Edu-sig] Pascal's Triangle (in 2.6)

[kirby urner]

"""
Rows of Pascal's Triangle

See:
http://en.wikipedia.org/wiki/Pascal%27s_triangle
"Calculating an individual row"

Consider a row starting as follows:
1, 12...

Initialize to [1] and multiply by (row_num/1)
to get the next term, row[1].

Then decrement and increment again, getting
(11 / 2), (10 / 3), (9 / 4) and so forth, and multiply
by the last term so far.  Stop when the numerator
is 0.

1 * (12/1) = 12
12 * (11 / 2) = 66
66 * (10 / 3) = 220
220 * (9 / 4) = 495

etc.

This is another way of computing successive values
of C(n, k) without using a factorial function and
dividing.

Independently discovered by David Koski,
implemented in Python by Kirby Urner

"""

def pascal_row(row_num):
    numer = row_num
    denom = 1
    # initialize row of Pascal's Triangle
    row = [1]
    while numer > 0:
        row.append((row[-1] * numer/denom))
        numer -= 1  # decrement numerator
        denom += 1  # increment denominator
    return row

def pascal_mod2(row_num = 0):
    """
    row integers mod 2, give a binary string which
    corresponds to Rule 60 in the Wolfram categorization
    scheme for cellular automata

    http://www.research.att.com/~njas/sequences/A001317
    """
    while True:
        therow = pascal_row(row_num)
        binary = "".join(str(i % 2) for i in therow)
        yield [int(binary,2), binary]
        row_num += 1

"""
traditional generator for successive rows, included
for completeness
"""

def pascal_gen():
    row = [1]
    while True:
        yield row
        row = [i + j for i,j in zip(row + [0], [0] + row)]