Python and Schools

Tim Peters tim.one at comcast.net
Fri Apr 18 03:45:08 CEST 2003


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

So the algorithm is

def anysame(seq):
    allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
    for i, x in enumerate(seq):
        if A[x] is an integer and 0 <= A[x] < i and seq[A[x]] == x:
            return True
        A[x] = i
    return False

Cute!  I like it.

> 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.

Yup, understood.  I still like it <wink>.





More information about the Python-list mailing list