generating points on a grid - efficiently

Rajarshi Guha rajarshi at presidency.com
Sat Mar 6 18:47:06 CET 2004


Hi, 
 I've written some code that takes a N lists of numbers (corresponding to
axes) and generates a list of grid points (N dimensional grid) for the
supplied axes. So as an example say my two axes are defined as

v1 = [1,2,3]
v2 = [1,2,3]

My code will return to me a list of points: 

(1,1), (1,2), (1,3) ....(3,1), (3,2), (3,3)

and so on. For 3 axes, I would obtain 27 points and so on.
I've included the code below.

My questions:

Firstly,  the code runs in exponential time. Is there any way to
rewrite it to make it more efficient? It seems that this could be
formulated as a recursive problem but I can't seem to get at it.

Secondly, it seems that the repeated use of copy.deepcopy() is very
wasteful? Is there a way I can get around it?

Thanks,

###########################

import copy

def extendgp(g,v):
    newg = []
    if not g:
        for i in v:
            newg.append( [i,] )
        return  newg

    for i in g:
        for j in v:
            x = copy.deepcopy(i)
            x.append(j)
            newg.append(x)
    return newg

def gengrid(axislist):

    grid = []
    for axes in axislist:
        grid = extendgp( grid, axes )
    return grid

if __name__ == '__main__':

    v1 = [1,2,3]
    v2 = [1,2,3]
    v3 = [1,2,3]

    grid = gengrid( (v1,v2,v3) )
    print grid




More information about the Python-list mailing list