tricky nested list unpacking problem

Reckoner reckoner at gmail.com
Tue Dec 16 04:21:01 CET 2008


On Dec 15, 1:28 pm, Arnaud Delobelle <arno... at googlemail.com> wrote:
> Reckoner<recko... at 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.



More information about the Python-list mailing list