tricky nested list unpacking problem

Discussion in 'Python' started by Reckoner, Dec 15, 2008.

  1. Reckoner

    Reckoner Guest

    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.
     
    Reckoner, Dec 15, 2008
    #1
    1. Advertising

  2. Reckoner

    Chris Rebert Guest

    On Mon, Dec 15, 2008 at 11:06 AM, Reckoner <> 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
     
    Chris Rebert, Dec 15, 2008
    #2
    1. Advertising

  3. Reckoner <> 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, 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']

    --
    Arnaud
     
    Arnaud Delobelle, Dec 15, 2008
    #3
  4. Reckoner

    Guest

    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
     
    , Dec 15, 2008
    #4
  5. Reckoner

    Chris Rebert Guest

    On Mon, Dec 15, 2008 at 12:24 PM, Kirk Strauser <> wrote:
    > At 2008-12-15T20:03:14Z, "Chris Rebert" <> 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
     
    Chris Rebert, Dec 16, 2008
    #5
  6. Reckoner

    Reckoner Guest

    On Dec 15, 1:28 pm, Arnaud Delobelle <> wrote:
    > Reckoner<> 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, 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']
    >
    > --
    > Arnaud


    Thanks for your detailed reply. I will have to ponder your solution
    carefully.
     
    Reckoner, Dec 16, 2008
    #6
  7. 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):
    for res in unpack(lst, acc + [x]):
    yield res

    --
    Arnaud
     
    Arnaud Delobelle, Dec 16, 2008
    #7
  8. Reckoner

    Steve Holden Guest

    Chris Rebert wrote:
    > On Mon, Dec 15, 2008 at 11:06 AM, Reckoner <> 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/
     
    Steve Holden, Dec 16, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Panos Laganakos

    Unpacking a list of strings

    Panos Laganakos, Apr 27, 2006, in forum: Python
    Replies:
    1
    Views:
    274
    Alex Martelli
    Apr 27, 2006
  2. Chris Garland

    Unpacking problem

    Chris Garland, Mar 1, 2007, in forum: Python
    Replies:
    3
    Views:
    320
  3. Replies:
    9
    Views:
    541
    CBFalconer
    Apr 25, 2006
  4. Ross
    Replies:
    15
    Views:
    678
    Vlastimil Brom
    Sep 22, 2009
  5. Josselin
    Replies:
    0
    Views:
    103
    Josselin
    Sep 24, 2007
Loading...

Share This Page