[Numpy-discussion] combinatorics

[Ernest Adrogué]

 4/03/10 @ 12:26 (+0100), thus spake Johan Grönqvist:
> Ernest Adrogué skrev:
> > Suppose I want to find all 2-digit numbers whose first digit
> > is either 4 or 5, the second digit being 7, 8 or 9.
> > 
> > I came up with this function, the problem is it uses recursion:
> > [...] 
> > In [157]: g([[4,5],[7,8,9]])
> > Out[157]: [[4, 7], [4, 8], [4, 9], [5, 7], [5, 8], [5, 9]]
> > 
> > Is important that it works with more than two sets too.
> > Any idea is appreciated.
> > 
> 
> 
> The one-line function defined below using only standard python seems to 
> work for me (CPython 2.5.5).
> 
> The idea you had was to first merge the two first lists, and then merge 
> the resulting lists with the third, and so on. This is exactly the idea 
> behind the reduce function, called fold in other languages, and you 
> recursive call can be replaced by a call to reduce.
> 
> / johan
> 
> 
> 
> ---------------------------------------------------
> In [5]: def a(xss):
>      return reduce(lambda xss, ys: [ xs + [y] for xs in xss for y in ys 
> ], xss, [[]])
>     ...:

Thanks. It took me a while to understand how it works :)

I have re-written your function using a for loop, which looks
less intimidating in my opinion.

def g(sets):
    out = [[]]
    for i in range(len(sets)):
        out = [j + [i] for i in sets[i] for j in out]
    return out

In [196]: g([[4,5], [7,8,9]])
Out[196]: [[4, 7], [5, 7], [4, 8], [5, 8], [4, 9], [5, 9]]


> In [7]: a([[4, 5], [7, 8, 9]])
> Out[7]: [[4, 7], [4, 8], [4, 9], [5, 7], [5, 8], [5, 9]]
> 
> In [8]: a([[4, 5], [7, 8, 9], [10, 11, 12, 13]])
> Out[8]:
> [[4, 7, 10],
>   [4, 7, 11],
>   [4, 7, 12],
>   [4, 7, 13],
>   [4, 8, 10],
>   [4, 8, 11],
>   [4, 8, 12],
>   [4, 8, 13],
>   [4, 9, 10],
>   [4, 9, 11],
>   [4, 9, 12],
>   [4, 9, 13],
>   [5, 7, 10],
>   [5, 7, 11],
>   [5, 7, 12],
>   [5, 7, 13],
>   [5, 8, 10],
>   [5, 8, 11],
>   [5, 8, 12],
>   [5, 8, 13],
>   [5, 9, 10],
>   [5, 9, 11],
>   [5, 9, 12],
>   [5, 9, 13]]
> --------------------------------------------
> 
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion