generating points on a grid - efficiently

Josiah Carlson jcarlson at nospam.uci.edu
Tue Mar 9 05:03:43 CET 2004


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

The code does not run in exponential time.  It runs in linear time to 
the number of grid points that exist.  Depending on your input, this can 
vary.

For example, let us say that I have two axes, X, Y (where X and Y are 
lists of grid points).  An optimal algorithm to generate all possible 
pairs will take len(X)*len(Y) time.

For three axes, X, Y, Z, it will take len(X)*len(Y)*len(Z) time.

In general, for k axes and lists of points all of length n, it will take 
O(n^k) time.

That is polynomial, not exponential.

  - Josiah



More information about the Python-list mailing list