[Numpy-discussion] Extracting all the possible combinations of a grid

[Gael Varoquaux]

On Fri, Sep 21, 2007 at 02:33:42PM -0600, Charles R Harris wrote:
>    I wrote up some of the combinatorial algorithms in python a few years ago
>    for my own use in writing a paper, ( Harris, C. R. Solution of the
>    aliasing and least squares problems of spaced antenna interferometric
>    measurements using lattice methods, Radio Sci. 38, 2003). I even thought I
>    had found an error and have a letter from Knuth pointing out that I was
>    mistaken ;) Anyway, there are a lot of neat things in volume 4 and it is
>    well worth the read. 

It is. I did my homework, and now I understand why you point this out.
Basically array programming is really not suited for these kind of
things. The problem with my solution is that is blows up the memory
really quickly. It is actually a pretty poor solution. It is obvious when
you think about this a bit that the problem diverges really quickly if
you try the brute force approach. It is actually really quick, until it
blows the memory.

I'll wait to know exactly what the numbers are (I am doing this to help a
friend), I see if I keep my kludge, if I use one a Knuth's nice
algorithms or if I simply implement a for loop in C + weave inline.

>    As to putting these things in scipy, I wouldn't mind at all if there
>    was a cs kit with various trees, union-find (equivalence relation)
>    structures, indexing, combinatorial generation, and graph
>    algorithms, but I am not sure how well they would fit in.

That would be great. I have wanted these things a few times. I am not
sure either how to fit them in. I don't really know how to fit graphs and
trees with arrays.

Thanks for your wise words,

Gaël