generating points on a grid - efficiently
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
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
That is polynomial, not exponential.
More information about the Python-list