combinations of variable length nested lists

[David C. Ullrich]

Well there's an obvious "just do it" recursive
version. Something like

def CartesianProduct(alist):

  res = []

  if len(alist) < 2:
    for x in alist[0]:
      res.append([x])
  else:
    tails = CartesianProduct(alist[1:])
    for x in alist[0]:
      for t in tails:
        res.append([x]+t)
    
  return res

print CartesianProduct([[1,2,3],[4,5], [6,7,8]])

seems to do what you seem to want. (That's not
supposed to be an optimal solution: it makes
a lot of assumptions about the input, and
no doubt it can be written in far fewer lines,
using the functional-programming functions 
and/or new-fangled Python... but it works, and
I think it's easy to see why it works. A "map"
in place of the first loop would probably be
quicker; I have no idea whether a list
comprehension in place of the second (double)
loop would be faster, because they have sometimes
turned out to be slower in places where you'd
think they'd be faster.)

On Tue, 07 Aug 2001 13:48:54 +0100, Mark Robinson
<m.1.robinson at herts.ac.uk> wrote:

>I have hurt my brain (and those who are unfortunate to sit near me ;)) 
>trying to formulate an algorithm for the following problem. I am sure 
>that someone here must be able to help me out, it seems such a trivial 
>problem.
>
>I have a nested list structure of the following format:
>[[2, 3, 4, 5],
>  [4, 5, 6, 7, 34],
>  [6, 2, 7, 4]
>  ....
>  ....
>]
>
>I want to generate all possible combinations that take one element from 
>each nested list
>
>i.e
>[2, 4, 6, ..., ...]
>[2, 4, 2, ..., ...]
>
>If I knew the length of the outermost list beforehand I could hard code 
>it as a series of nested for loops:
>
>i.e
>
>for i in list[0]:
>	for j in list[1]:
>		for k in list[2]:
>				comb = [i, j, k]
>
>but I can't figure a way to do this dynamically at runtime, when the 
>outermost list is going to be variable in length.
>
>If anyone can help, I'll be willing to sell my boss into slavery and 
>give you all the profit ;)

Probably the simplest thing is if you send the check to David Ullrich
at "Department of Mathematics, OSU, Stillwater, OK 74078". Thanks.

>Blobby
>


David C. Ullrich