Traversing Lists of Lists

[shadypalm88]

Hi, guys. I'm racking my brain trying to figure out a generic way to do what the following Python code does for lists of three lists. I could just be stressed out and lacking sleep, but I don't see a good way!

Code Select Expand

possibles = ['ABCDE', '12345', 'XYZ']

def compute_paths(lst):
paths = []

for a in lst[0]:
for b in lst[1]:
for c in lst[2]:
paths.append([a, b, c])

return paths

for path in compute_paths(possibles):
print ''.join(path)

This correctly outputs:

Code Select Expand

A1X
A1Y
A1Z
A2X
A2Y
...
E4Y
E4Z
E5X
E5Y
E5Z

but I need to do it for any complexity. Thoughts?

[Kp]

How about this?  The level of indirection for the resulting list is a bit off, but that's a minor detail that you can fix if you care.

Code Select Expand


l = ['AB', '12', 'XZ']

def increment(i, c):
while c >= 0:
i[c] = i[c] + 1
if i[c] >= len(l[c]):
i[c], c = 0, c - 1
else:
break
return c

if len(l) <= 0:
sys.exit(0)
r = range(0, len(l))

p = []

i = [0 for c in r]
while True:
p.append([l[c][i[c]] for c in r])
if increment(i, c) < 0:
break
print p


Sample output:

Code Select Expand

[['A', '1', 'X'], ['A', '1', 'Z'], ['A', '2', 'X'], ['A', '2', 'Z'], ['B', '1', 'X'], ['B', '1', 'Z'], ['B', '2', 'X'], ['B', '2', 'Z']]

[Insolence]

Not sure about any specific Python code, but you definitely want a recursive function--I think.

[MyndFyre]

Not sure about any specific Python code, but you definitely want a recursive function--I think.

Recursion, but Python has access to functional constructs that would make code a bit more elegant than procedural recursion.   

But yes, recursion should be the way to go in this case, unless you're going to be nested on more than a couple orders of magnitude of complexity.

[Banana fanna fo fanna]

Code Select Expand


possibles = ["ABCDE","12345","XYZ"]

def compute_paths(lst):
if len(lst) == 1:
return [[x] for x in lst[0]]
else:
r = []
for tail in compute_paths(lst[1:]):
for e in lst[0]:
r.append([e] + tail)
return r

for path in compute_paths(possibles):
print "".join(path)



[Joe[x86]]

Not sure about any specific Python code, but you definitely want a recursive function--I think.

You realize that's an oxymoron, right?

[squeegee]

x86] link=topic=16744.msg169606#msg169606 date=1180734812]

Not sure about any specific Python code, but you definitely want a recursive function--I think.

You realize that's an oxymoron, right?

Python has some functional programming aspects, but it's not like say Haskell