- **Python**
(*http://www.velocityreviews.com/forums/f43-python.html*)

- - **tricky nested list unpacking problem**
(*http://www.velocityreviews.com/forums/t648772-tricky-nested-list-unpacking-problem.html*)

tricky nested list unpacking problemHi,
I have lists of the following type: [1,2,3,[5,6]] and I want to produce the following strings from this as '0-1-2-3-5' '0-1-2-3-6' That was easy enough. The problem is that these can be nested. For example: [1,2,3,[5,6],[7,8,9]] which should produce '0-1-2-3-5-7' '0-1-2-3-5-8' '0-1-2-3-5-9' '0-1-2-3-6-7' '0-1-2-3-6-8' '0-1-2-3-6-9' also, [1,2,3,[5,6],7,[9]] should produce '0-1-2-3-5-7-9' '0-1-2-3-6-7-9' obviously, these are nested loops over the lists. The problem is that I don't know ahead of time how many lists there are or how deep they go. In other words, you could have: [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] Any help appreciated. I've really been having trouble with this. I hope that made sense. |

Re: tricky nested list unpacking problemOn Mon, Dec 15, 2008 at 11:06 AM, Reckoner <reckoner@gmail.com> wrote:
> Hi, > > I have lists of the following type: > > [1,2,3,[5,6]] > > and I want to produce the following strings from this as > > '0-1-2-3-5' > '0-1-2-3-6' > > That was easy enough. The problem is that these can be nested. For > example: > > [1,2,3,[5,6],[7,8,9]] > > which should produce > > '0-1-2-3-5-7' > '0-1-2-3-5-8' > '0-1-2-3-5-9' > '0-1-2-3-6-7' > '0-1-2-3-6-8' > '0-1-2-3-6-9' > > also, > > [1,2,3,[5,6],7,[9]] > > should produce > > '0-1-2-3-5-7-9' > '0-1-2-3-6-7-9' > > obviously, these are nested loops over the lists. The problem is that > I don't know ahead of time how many lists there are or how deep they > go. In other words, you could have: > > [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] > > Any help appreciated. I've really been having trouble with this. > > I hope that made sense. You just need a recursive list-flattening function. There are many recipes for these. Here's mine: def flatten(lst): if isinstance(lst, list): result = [] for item in lst: result += flatten(item) return result else: return [lst] >>> flattened = flatten([1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]]) >>> flattened [1, 2, 3, 5, 6, 10, 11, 7, 9, 1, 2, 3, 4, 5] >>> '-'.join(str(num) for num in flattened) '1-2-3-5-6-10-11-7-9-1-2-3-4-5' Cheers, Chris -- Follow the path of the Iguana... http://rebertia.com |

Re: tricky nested list unpacking problemReckoner <reckoner@gmail.com> writes:
> Hi, > > I have lists of the following type: > > [1,2,3,[5,6]] > > and I want to produce the following strings from this as > > '0-1-2-3-5' > '0-1-2-3-6' > > That was easy enough. The problem is that these can be nested. For > example: > > [1,2,3,[5,6],[7,8,9]] > > which should produce > > '0-1-2-3-5-7' > '0-1-2-3-5-8' > '0-1-2-3-5-9' > '0-1-2-3-6-7' > '0-1-2-3-6-8' > '0-1-2-3-6-9' > > also, > > [1,2,3,[5,6],7,[9]] > > should produce > > '0-1-2-3-5-7-9' > '0-1-2-3-6-7-9' > > obviously, these are nested loops over the lists. The problem is that > I don't know ahead of time how many lists there are or how deep they > go. In other words, you could have: > > [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] IMHO the second level of nested lists is unnecessary as the same can be achieved with just one sublevel of list (unless they are to be interpreted in a way you have not explained). If you avoid this double nesting then the 'flatten()' function below is not necessary anymore. > > Any help appreciated. I've really been having trouble with this. > > I hope that made sense. Here is a not thought out solution: def flatten(lst): for x in lst: if isinstance(x, list): for y in flatten(x): yield y else: yield x def unpack(lst): stack, strings = [], [] def rec(): i = len(stack) if i == len(lst): strings.append('-'.join(map(str, stack))) elif isinstance(lst[i], list): for x in flatten(lst[i]): stack.append(x) rec() stack.pop() else: stack.append(lst[i]) rec() rec() return strings l1 = [1,2,3,[5,6]] l2 = [1,2,3,[5,6],[7,8,9]] l3 = [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] Then: >>> unpack(l1) ['1-2-3-5', '1-2-3-6'] >>> unpack(l2) ['1-2-3-5-7', '1-2-3-5-8', '1-2-3-5-9', '1-2-3-6-7', '1-2-3-6-8', '1-2-3-6-9'] >>> unpack(l3) ['1-2-3-5-7-9', '1-2-3-5-7-1', '1-2-3-5-7-2', '1-2-3-5-7-3', '1-2-3-5-7-4', '1-2-3-5-7-5', '1-2-3-5-6-9', '1-2-3-5-6-1', '1-2-3-5-6-2', '1-2-3-5-6-3', '1-2-3-5-6-4', '1-2-3-5-6-5', '1-2-3-5-10-9', '1-2-3-5-10-1', '1-2-3-5-10-2', '1-2-3-5-10-3', '1-2-3-5-10-4', '1-2-3-5-10-5', '1-2-3-5-11-9', '1-2-3-5-11-1', '1-2-3-5-11-2', '1-2-3-5-11-3', '1-2-3-5-11-4', '1-2-3-5-11-5'] -- Arnaud |

Re: tricky nested list unpacking problemArnaud Delobelle:
> Here is a not thought out solution: >... I was waiting to answer because so far I have found a bad-looking solution only. Seeing there's only your solution, I show mine too. It seems similar to your one. def xflatten(seq): if isinstance(seq, list): stack = [iter(seq)] while stack: for item in stack[-1]: if isinstance(item, list): stack.append(iter(item)) break yield item else: stack.pop() else: yield seq def product(pools): if isinstance(pools, list): result = [[]] for pool in pools: if isinstance(pool, list): result = [x+[y] for x in result for y in xflatten(list (product(pool)))] else: result = [x+[pool] for x in result] for prod in result: yield prod else: yield pools s1 = [1,[2, 3, 4], 5,[6, 7]] s2 = [1,[2, [3, 4]], 5,[6,7],8,[9]] s3 = [1,2,3,[4,5,[6, 7]],8,[9,[10, 11, 12, 13, 14]]] def stringify(seq): for el in product(seq): yield "0-" + "-".join(map(str, el)) for seq in [s1, s2, s3]: for txt in stringify(seq): print txt It's ugly, I agree. No much tested. *surely* there are shorter and much nicer solutions. It reminds me the exercises of the "Little Schemer" :-) Bye, bearophile |

Re: tricky nested list unpacking problemOn Mon, Dec 15, 2008 at 12:24 PM, Kirk Strauser <kirk@daycos.com> wrote:
> At 2008-12-15T20:03:14Z, "Chris Rebert" <clp@rebertia.com> writes: > >> You just need a recursive list-flattening function. There are many >> recipes for these. Here's mine: > >>>>> flattened = flatten([1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]]) >>>>> flattened >> [1, 2, 3, 5, 6, 10, 11, 7, 9, 1, 2, 3, 4, 5] >>>>> '-'.join(str(num) for num in flattened) >> '1-2-3-5-6-10-11-7-9-1-2-3-4-5' > > He doesn't want to flatten them directly. He's using [1,2,3] sort of like a > regular expression, so that 1,[2,3],4 means "1,2,4" or "1,3,4", not > "1,2,3,4". Ah, my bad. Misinterpreted. Still, it's a similar principle involved. He just needs to code up the right recursive function. Not all that hard. Cheers, Chris -- Follow the path of the Iguana... http://rebertia.com |

Re: tricky nested list unpacking problemOn Dec 15, 1:28*pm, Arnaud Delobelle <arno...@googlemail.com> wrote:
> Reckoner<recko...@gmail.com> writes: > > Hi, > > > I have lists of the following type: > > > [1,2,3,[5,6]] > > > and I want to produce the following strings from this as > > > '0-1-2-3-5' > > '0-1-2-3-6' > > > That was easy enough. The problem is that these can be nested. For > > example: > > > [1,2,3,[5,6],[7,8,9]] > > > which should produce > > > '0-1-2-3-5-7' > > '0-1-2-3-5-8' > > '0-1-2-3-5-9' > > '0-1-2-3-6-7' > > '0-1-2-3-6-8' > > '0-1-2-3-6-9' > > > also, > > > [1,2,3,[5,6],7,[9]] > > > should produce > > > '0-1-2-3-5-7-9' > > '0-1-2-3-6-7-9' > > > obviously, these are nested loops over the lists. The problem is that > > I don't know ahead of time how many lists there are or how deep they > > go. In other words, you could have: > > > [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] > > IMHO the second level of nested lists is unnecessary as the same can be > achieved with just one sublevel of list (unless they are to be > interpreted in a way you have not explained). *If you avoid this double > nesting then the 'flatten()' function below is not necessary anymore. > > > > > Any help appreciated. I've really been having trouble with this. > > > I hope that made sense. > > Here is a not thought out solution: > > def flatten(lst): > * * for x in lst: > * * * * if isinstance(x, list): > * * * * * * for y in flatten(x): > * * * * * * * * yield y > * * * * else: > * * * * * * yield x > > def unpack(lst): > * * stack, strings = [], [] > * * def rec(): > * * * * i = len(stack) > * * * * if i == len(lst): > * * * * * * strings.append('-'.join(map(str, stack))) > * * * * elif isinstance(lst[i], list): > * * * * * * for x in flatten(lst[i]): > * * * * * * * * stack.append(x) > * * * * * * * * rec() > * * * * * * * * stack.pop() > * * * * else: > * * * * * * stack.append(lst[i]) > * * * * * * rec() > * * rec() > * * return strings > > l1 = [1,2,3,[5,6]] > l2 = [1,2,3,[5,6],[7,8,9]] > l3 = [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] > > Then: > > >>> unpack(l1) > > ['1-2-3-5', '1-2-3-6']>>> unpack(l2) > > ['1-2-3-5-7', '1-2-3-5-8', '1-2-3-5-9', '1-2-3-6-7', '1-2-3-6-8', '1-2-3-6-9']>>> unpack(l3) > > ['1-2-3-5-7-9', '1-2-3-5-7-1', '1-2-3-5-7-2', '1-2-3-5-7-3', > '1-2-3-5-7-4', '1-2-3-5-7-5', '1-2-3-5-6-9', '1-2-3-5-6-1', > '1-2-3-5-6-2', '1-2-3-5-6-3', '1-2-3-5-6-4', '1-2-3-5-6-5', > '1-2-3-5-10-9', '1-2-3-5-10-1', '1-2-3-5-10-2', '1-2-3-5-10-3', > '1-2-3-5-10-4', '1-2-3-5-10-5', '1-2-3-5-11-9', '1-2-3-5-11-1', > '1-2-3-5-11-2', '1-2-3-5-11-3', '1-2-3-5-11-4', '1-2-3-5-11-5'] > > -- > Arnaud Thanks for your detailed reply. I will have to ponder your solution carefully. |

Re: tricky nested list unpacking problembearophileHUGS@lycos.com writes:
> I was waiting to answer because so far I have found a bad-looking > solution only. Seeing there's only your solution, I show mine too. It > seems similar to your one. I think that the solution below is a bit clearer, although I think it is more resource intensive than my first one. I've switched to a generator function to make it more easily comparable. It's true that it's a problem that seems designed for Scheme! l1 = [1,2,3,[5,6]] l2 = [1,2,3,[5,6],[7,8,9]] l3 = [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] def flatten(x): if isinstance(x, list): for y in x: for z in flatten(y): yield z else: yield x def unpack(lst, acc=[]): i = len(acc) if i == len(lst): yield '-'.join(map(str, acc)) else: for x in flatten(lst[i]): for res in unpack(lst, acc + [x]): yield res -- Arnaud |

Re: tricky nested list unpacking problemChris Rebert wrote:
> On Mon, Dec 15, 2008 at 11:06 AM, Reckoner <reckoner@gmail.com> wrote: >> Hi, >> >> I have lists of the following type: >> >> [1,2,3,[5,6]] >> >> and I want to produce the following strings from this as >> >> '0-1-2-3-5' >> '0-1-2-3-6' >> >> That was easy enough. The problem is that these can be nested. For >> example: >> >> [1,2,3,[5,6],[7,8,9]] >> >> which should produce >> >> '0-1-2-3-5-7' >> '0-1-2-3-5-8' >> '0-1-2-3-5-9' >> '0-1-2-3-6-7' >> '0-1-2-3-6-8' >> '0-1-2-3-6-9' >> >> also, >> >> [1,2,3,[5,6],7,[9]] >> >> should produce >> >> '0-1-2-3-5-7-9' >> '0-1-2-3-6-7-9' >> >> obviously, these are nested loops over the lists. The problem is that >> I don't know ahead of time how many lists there are or how deep they >> go. In other words, you could have: >> >> [1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]] >> >> Any help appreciated. I've really been having trouble with this. >> >> I hope that made sense. > > You just need a recursive list-flattening function. There are many > recipes for these. Here's mine: > > def flatten(lst): > if isinstance(lst, list): > result = [] > for item in lst: > result += flatten(item) > return result > else: > return [lst] > >>>> flattened = flatten([1,2,3,[5,6,[10, 11]],7,[9,[1, 2, 3, 4, 5 ]]]) >>>> flattened > [1, 2, 3, 5, 6, 10, 11, 7, 9, 1, 2, 3, 4, 5] >>>> '-'.join(str(num) for num in flattened) > '1-2-3-5-6-10-11-7-9-1-2-3-4-5' > Read the problem description again ... regards Steve -- Steve Holden +1 571 484 6266 +1 800 494 3119 Holden Web LLC http://www.holdenweb.com/ |

All times are GMT. The time now is 04:55 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.