Python and Schools

[David Eppstein]

In article <mailman.1050604354.15055.python-list at python.org>,
 Tim Peters <tim.one at comcast.net> wrote:

> >     for i,x in enumerate(seq):
> >         if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
> >             return True
> >         A[x] = i
> >     return False
> 
> Something must be missing here, right?  For example, suppose A just happens
> to be uninitialized to all zeroes, and we pass in seq=[8, 8].  Then A[8] is
> set to 0 in the first loop trip, and in the second
> 
>     A[8] is 0 so 0 <= A[x] < i is true
>     A[A[x]] == A[A[8]] == A[0] == 0 != 8 so the if guard is false
>     A[8] is set to 1
> 
> Then the loop ends and the function returns False.

Sorry, bug in untested code.  Instead of A[A[x]]==x the test should be 
seq[A[x]]==x.

Anyway, this is not code you would want to actually use, just an 
illustration of how random access can sometimes make it useful to have 
much more memory than you actually touch during an algorithm.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science