tricky nested list unpacking problem

[Reckoner]

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.

 

[Chris Rebert]

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

 

[Arnaud Delobelle]

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, list):
for x in flatten(lst):
stack.append(x)
rec()
stack.pop()
else:
stack.append(lst)
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']

 

[bearophileHUGS]

Arnaud 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
print

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

 

[Chris Rebert]

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

 

[Reckoner]

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, list):
            for x in flatten(lst):
                stack.append(x)
                rec()
                stack.pop()
        else:
            stack.append(lst)
            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:

['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']

Thanks for your detailed reply. I will have to ponder your solution
carefully.

 

[Arnaud Delobelle]

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):
for res in unpack(lst, acc + [x]):
yield res

 

[Steve Holden]

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