# [Numpy-discussion] combinatorics

Johan Grönqvist johan.gronqvist@gmail....
Thu Mar 4 05:26:25 CST 2010

```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, [[]])
...:

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]]
--------------------------------------------

```