tricky nested list unpacking problem

[Arnaud Delobelle]

Reckoner <reckoner 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