[Numpy-discussion] combinatorics

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

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