tricky nested list unpacking problem
Reckoner
reckoner at gmail.com
Mon Dec 15 22:21:01 EST 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