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

[Gael Varoquaux]

On Fri, Sep 21, 2007 at 01:52:31PM -0600, Charles R Harris wrote:
>    Go here, http://www.cs.utsa.edu/~wagner/knuth/. I think you want fascicle
>    4A, http://www.cs.utsa.edu/~wagner/knuth/fasc4a.pdf. Some of the fascicles
>    from Vol 4 of TAOCP are now in print, http://tinyurl.com/2goxpr.

:->. That's the best answer I have ever had so far: RTFAOCP !

OK, I'll have a look, but I'd be surprised he talks about loop free ways.

Anyhow, I have kludged a solution that seems to be working. Not the most
beautiful ever, but it seems to be working. I will need to time it, but
first I need to ask the end user what the actual numbers are.

Here is the kludge, feel free to lough:

+++++++++++++++++++++++++++++++++++++++++++++++++++++
from numpy import reshape, indices, arange, take, diff

def unique_nplets(size, dims):
    """ Generate all the possible unique combinations of n=dims integers
    below size.
    """
    # Generate all the possible nplets
    ##triplets = reshape(mgrid[0:2, 0:2, 0:2], (3, -1))
    nplets = reshape(indices(dims*[size,]), (dims, -1))
    # Sort them
    nplets.sort(axis=0)
    nplets.sort(axis=-1)
    # Compare succesive columns using the diff, than sum the diff (all
    # positiv
    # numbers), is the sum is not zero, the columns are different, make a
    # mask out of this condition, and apply it to arange to retrieve the
    # indices of these columns
    unique_indices = arange(size**dims)[(diff(nplets).sum(axis=0) > 0)]
    # Retrieve the unique columns
    unique_nplets = take(nplets, unique_indices, axis=-1)
    return unique_nplets
+++++++++++++++++++++++++++++++++++++++++++++++++++++

I was actually excepting numpy (or scipy) to have functions built-in for
these kind of problems. Or to have people on the list having already done
this.

Thanks for the reply, I will indeed look it up.

Gaël