[Edu-sig] Re: re: Python as a first-year programming language (Terry Hancock)

[Toby Donaldson]

On Monday 28 April 2003 09:29 am, Kirby Urner wrote:
> > On Monday 28 April 2003 01:37 am, Toby Donaldson wrote:
> > Is there any way in Python to implement
> non-deterministic
> > > programming, e.g. for backtacking? It would be nice to
> be able to write
> > > something like this:
> > >
> > >   def triple(a, b, c, n):
> > >     a = choice(n)    # choice non-deterministically
> chooses a number from 0
> > > to n-1
> > >     b = choice(n)
> > >     c = choice(n)
> > >     if a**2 + b**2 == c**2:
> > >       return a, b, c
> >
> > You're asking if Python can do pseudo-random numbers?
>
> Assuming that you *did* mean this, Toby, you should be aware
> that your function can be written almost exactly as you
> just did:
>
> from random import choice
>
> def triple(n):
>     a = choice(range(n))
>     b = choice(range(n))
>     c = choice(range(n))
>     if a**2 + b**2 == c**2:
>         return a, b, c
>
> Try it.  ;-)
> >>> triple(3)
> >>> triple(3)
> (2, 0, 2)
> >>> triple(3)
> (1, 0, 1)
> >>> triple(3)
> >>> triple(3)
> (0, 0, 0)


Actually, I mean non-deterministic in the sense of backtracking, as in
Prolog. For instance, it would be nice if I could write this

def triple(n):  # doh: had extraneous parameters in the original version
  a = choice(n)    # non-deterministically chooses a number from 0 to n-1
  b = choice(n)
  c = choice(n)
  if a**2 + b**2 == c**2:
    return a, b, c

and use it like this:

>>> fn = triple(4)
>>> fn.next()
(0, 0, 0)
>>> fn.next()
(0, 1, 1)
>>> fn.next()
(0, 2, 2)

... etc. ...

The pseudocode in Norvig & Russel's AI book (1st edition, at least) uses
"choice" to make certain algorithms must shorter looking.

Scheme lets you implement this in about a dozen lines of code. It comes for
free in Prolog. This is one reason why Scheme and Prolog are so wicked cool.
:-)

See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3
for more details ...

Actually, Python's list comprehensions and generators, can get you close in
some cases. The above triple function can actually be implemented like this:

def triple(n):
    """ Generates all Pythagorean triples a, b, c such that:
          - a^2 + b^2 = c^2
          - a in range(n), b in range(n), c in range(n)
    """
    for a in xrange(n):
        for b in xrange(n):
            for c in xrange(n):
                if a ** 2 + b ** 2 == c ** 2:
                    yield a, b, c

Toby