number generator

[Paul Rubin]

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))]

I'm not sure which is better from a Python stylistic perspective.
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.

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.