number generator

[Dick Moores]

At 06:20 PM 3/13/2007, Paul Rubin wrote:
>Dick Moores <rdm at rcblue.com> writes:
> > I understand what zip() and random.sample() are doing, and the above
> > helps me get inside the fencepost method, but I don't understand WHY
> > it works, or how in the world anyone could have devised it. It is
> > truly magical to me!
>
>It's Gerald Flanagan's telegraph pole method that you quoted (I
>misremembered it as "fencepost"):
>
>     "Suppose you have a fixed telegraph pole at N and a fixed telegraph
>     pole at M, and you're given 5 more telegraph poles..." (Gerard Flanagan),
>
>Consider this diagram for the numbers from 1 to 50:
>
>   |--------------------------------------------------|
>
>The vertical bar at the left represents 0 and the vertical bar
>at the right represents 51.  The fifty dashes represent 1,2,3...50.
>You can also view the fifty dashes as a line segment of length 50.
>
>The fencepost method is to simply chop the line segment into smaller
>pieces.  You do that by choosing some random points inside the segment:
>
>     >>> import random
>     >>> random.sample(xrange(1,50), 4)
>     [49, 37, 22, 5]
>
>so mark those points with plus signs (let's see if I got this right)
>and label the points from left to right, calling them p0,p1,p2,p3:
>
>     |----+----------------+--------------+-----------+-|
>          p0               p1             p2          p3
>
>So the length of the leftmost small segment is p0-0, the length of the
>second segment is p1-p0, the third is p2-p1, the fourth is p3-p2, and
>the fifth is 50-p3.  So those lengths are the numbers you want.
>
>The zip thing was just a way to avoid using messy subscripts to
>compute the lengths.  Another way to do it is (untested):
>
>    t2 = [0] + t + [50]
>    lst = [(t2[i] - t2[i-1]) for i in xrange(1, len(t2))]

Works fine!

>I'm not sure which is better from a Python stylistic perspective.

I'm not sure, but I think if you had written it this way at first, I 
would have understood it.  But I'm glad to have learned the zip way!

>Using zip that way is fairly natural in Haskell, which I've been
>fooling around with lately.  All you're doing is subtracting adjacent
>elements by making two versions of the list, one of them shifted over
>one place, then subtracting element by element, instead of jumping
>around inside a single list, with more ways to make off-by-one errors.
>It looked more symmetrical in the Python code so I did it that way.

Thank you, thank you! You've made it very clear up to this point. 
I'll worry about the Haskell approach later, much later. ;)

Dick Moores

>FWIW, the actual Haskell approach would translate to something more like:
>
>    from itertools import chain, izip
>    lst = [(j-i) for i,j in izip(chain([0],t), chain(t,[50]))]
>
>which avoids making the intermediate zipped list.