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

[Charles R Harris]

On 9/21/07, Gael Varoquaux <gael.varoquaux@normalesup.org> wrote:
>
> On Fri, Sep 21, 2007 at 02:58:43PM -0600, Charles R Harris wrote:
> >    I found generators a good approach to this  sort of thing:
>
> >    for (i,j,k) in triplets(n) :
>
> That's what we where doing so far, but in the code itself. The result was
> unbearably slow.
> I think for our purposes we should build a precalculated table of these
> nuplets, and then do array calculations on them.
>
> I was just wondering what the good way to build this table was. And I
> immediately thought of using tricks on arrays without realizing the speed
> at which the combination diverged.
>
> In the worst case, a set of nested for loops in a weave.inline wrapped C
> code populating an array of (n**d/n!, d) size would do the trick and be
> real fast. Something like (implemented in C, rather than Python):
>
> index = 0
> for i in xrange(n):
>     for j in xrange(i):
>         for k in xrange(j):
>             index += 1
>             out_array(index, 0) = i
>             out_array(index, 1) = j
>             out_array(index, 2) = k
>
> This would scale pretty well IMHO.


Try

def triplet(n) :
    out = []
    for i in xrange(2,n) :
        for j in xrange(1,i) :
            for k in xrange(0,j) :
                out.append((i,j,k))
    return out

It's the first algorithm in Knuth, mentioned in passing.

In [7]: time a = triplet(100)
CPU times: user 0.14 s, sys: 0.01 s, total: 0.14 s
Wall time: 0.15

Which isn't too bad for 161700 combinations. However, I still prefer the
generator form if you want to save memory for large n.

In [2]: def triplet(n) :
   ...:     for i in xrange(2,n) :
   ...:         for j in xrange(1,i) :
   ...:             for k in xrange(1,j) :
   ...:                 yield i,j,k
   ...:

It's a bit slower for making lists, however.

In [24]: time for i,j,k in triplet(100) : a.append((i,j,k))
CPU times: user 0.24 s, sys: 0.01 s, total: 0.25 s
Wall time: 0.25

The more general algorithm L isn't too bad either

In [29]: def combination(n,t) :
   ....:     c = arange(t + 2)
   ....:     c[-1] = 0
   ....:     c[-2] = n
   ....:     while 1 :
   ....:         yield c[:t]
   ....:         j = 0
   ....:         while c[j] + 1 == c[j+1] :
   ....:             c[j] = j
   ....:             j += 1
   ....:         if j >= t :
   ....:             return
   ....:         c[j] += 1

In [30]: for i in combination(5,3) : print i
   ....:
[0 1 2]
[0 1 3]
[0 2 3]
[1 2 3]
[0 1 4]
[0 2 4]
[1 2 4]
[0 3 4]
[1 3 4]
[2 3 4]

In [31]: time for i in combination(100,3) : pass

CPU times: user 0.58 s, sys: 0.02 s, total: 0.60 s
Wall time: 0.60


Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://projects.scipy.org/pipermail/numpy-discussion/attachments/20070921/d7da87f7/attachment.html