Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   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)

Reckoner 12-15-2008 07:06 PM

tricky nested list unpacking problem
 
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 12-15-2008 08:03 PM

Re: tricky nested list unpacking problem
 
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'

Cheers,
Chris

--
Follow the path of the Iguana...
http://rebertia.com

Arnaud Delobelle 12-15-2008 09:28 PM

Re: tricky nested list unpacking problem
 
Reckoner <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

bearophileHUGS@lycos.com 12-15-2008 11:24 PM

Re: tricky nested list unpacking problem
 
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 12-16-2008 01:13 AM

Re: tricky nested list unpacking problem
 
On 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

Reckoner 12-16-2008 03:21 AM

Re: tricky nested list unpacking problem
 
On 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.

Arnaud Delobelle 12-16-2008 10:15 AM

Re: tricky nested list unpacking problem
 
bearophileHUGS@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

Steve Holden 12-16-2008 05:18 PM

Re: tricky nested list unpacking problem
 
Chris 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.