Pascal's Triangle (in 2.6)

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Pascal's Triangle (in 2.6)

kirby urner-4
"""
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)]
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Pascal's Triangle (in 2.6)

Mokurai
Pascal's Triangle mod 2 is also a Sierpinski gasket fractal. This is
one of the Python examples in Pippy in the Sugar education software.

# Sierpinski triangles
import sys
size = 3
modulus = 2

lines = modulus**size

vector = [1]
for i in range(1,lines+1):
  vector.insert(0,0)
  vector.append(0)

for i in range(0,lines):
  newvector = vector[:]
  for j in range(0,len(vector)-1):
    if (newvector[j] == 0):
      print " ",
    else:
      remainder = newvector[j] % modulus
      if (remainder == 0):
        print "O",
      else:
        print ".",
    newvector[j] = vector[j-1] + vector[j+1]
  print
  vector = newvector[:]

On Sat, Jan 30, 2010 at 12:23, kirby urner <[hidden email]> wrote:

This process below is how I learned Pascal's Triangle from my mother
when I was 11.

> """
> 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)]
> _______________________________________________
> Edu-sig mailing list
> [hidden email]
> http://mail.python.org/mailman/listinfo/edu-sig
>



--
Edward Mokurai (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) Cherlin
Silent Thunder is my name, and Children are my nation.
The Cosmos is my dwelling place, the Truth my destination.
http://www.earthtreasury.org/
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig
Reply | Threaded
Open this post in threaded view
|

Re: Pascal's Triangle (in 2.6)

kirby urner-4
On Sat, Jan 30, 2010 at 11:21 AM, Edward Cherlin <[hidden email]> wrote:
> Pascal's Triangle mod 2 is also a Sierpinski gasket fractal. This is
> one of the Python examples in Pippy in the Sugar education software.
>

Glad to see OLPC is getting the right stuff here.

Your technique of backing everything with a rectangular array of 'O's, to
be replaced by " ", "." or left alone, is a great way of formatting.  You use
"print comma" (print ,) to keep going on the line, no newline character
before we're done in that loop.

The same matting technique could be used for any rule-based row-by-row
generating scheme, ala the Wolfram numbering using a bit pattern to
encode the next permutation.  I've done some work in this area in collaboration
with other contributors to this archive (John Zelle, Gregor Lingl).

4dsolutions.net/ocn/python/nks.py
http://4dsolutions.net/ocn/python/canvas3.py

(note our back ending into PIL, Zelle's graphics.py or Gregor's wrapper for
TkCanvas).

Your use of a matte also mirrors my recent suggestion regarding building
a "color sniffing" turtle that stores a shared "canvas" object in some array,
perhaps of just integers, or RGB 3-tuples, if that's the only data we care
about (in addition to geographic position).

Turtles all read and write to the same matte through a handle (easy in
Python as the default is to not copy).

I did run it with gusto.  Might've been a dot missing lower right?

>>>
                .
              .   .
            .   O   .
          .   .   .   .
        .   O   O   O   .
      .   .   O   O   .   .
    .   O   .   O   .   O   .
  .   .   .   .   .   .   .   .
>>>

Great work.

Kirby

PS:

<geometry type="esoteric">

Pascal's is coming up in my research because I'm trying to do some
technical writing about one David Koski's studies.  He builds hexahedra
(zonohedral rhomb-faced) from great circle networks, packs them out to
the first spherical polyhedron, is finding some pattern in Pascal's that
predicts how many.

Example, when you use 10 mid-face axials of the icosahedron as a
set of spokes from the origin, illuminate any three not at 180 degrees,
you get successive corners of hexahedra, I think he said only 10
possible?

You get a rhombic dodecahedron inside the enneacontahedron that
way (as one of the zonohedra).  You get cubes inside the great
rhombicosadodecahedron.  Hope I got that right, will double check
with DAve.

The resulting spherical polyhedra may not have all rhombic faces however
as "zero volume" flattened hexahedra, predicted by Pascal's, come together
in the form of other polygons.  Here are a couple examples:

http://www.flickr.com/photos/17157315@N00/4279038891/in/set-72157622797118549/
(132 sides)

http://www.flickr.com/photos/17157315@N00/4311083958/in/set-72157622797118549/
(600 sides)

http://mybizmo.blogspot.com/2008/11/enneacontahedron.html
(older study)

</geometry>

> # Sierpinski triangles
> import sys
> size = 3
> modulus = 2
>
> lines = modulus**size
>
> vector = [1]
> for i in range(1,lines+1):
>  vector.insert(0,0)
>  vector.append(0)
>
> for i in range(0,lines):
>  newvector = vector[:]
>  for j in range(0,len(vector)-1):
>    if (newvector[j] == 0):
>      print " ",
>    else:
>      remainder = newvector[j] % modulus
>      if (remainder == 0):
>        print "O",
>      else:
>        print ".",
>    newvector[j] = vector[j-1] + vector[j+1]
>  print
>  vector = newvector[:]
>
> On Sat, Jan 30, 2010 at 12:23, kirby urner <[hidden email]> wrote:
>
> This process below is how I learned Pascal's Triangle from my mother
> when I was 11.
>

<< SNIP >>

> --
> Edward Mokurai (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) Cherlin
> Silent Thunder is my name, and Children are my nation.
> The Cosmos is my dwelling place, the Truth my destination.
> http://www.earthtreasury.org/
>
_______________________________________________
Edu-sig mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/edu-sig