Python: multilevel nested lists

Question

Possible Duplicate:
Flatten (an irregular) list of lists in Python

Example 1:

Lets say I have a list: [[1,2], [3,4]]. I could use two for loops to be able to print out: 1, 2, 3, 4.

Example 2:

So, now let's suppose that I'm given an output and I don't know how many nested lists there within list1:

list1 = [1, [1, 2, [3, 5, 6,[ .. ], ..., ] ] ] ] ]

So, my question is how would I be able to print out every individual number in the same format as the first example. I'm working with something right now that gives me nested lists as a result, but different inputs to the function will give me different amount of nested lists.

What I can think of is to do this, but I don't know what to do after the isinstance part:

c = 0
for i in list1:
   while c < len(list1):
         if isinstance(i, list):

         else:
              print i
         c += 1

Thanks

First Edit

If there is also a way to deconstruct all the nested lists to become a single list that would work as well for me, but I'm curious to know answers to both these problems.

Wow, thank you all. All of the answers below worked for me, but if I'm calculating correctly, the algorithm big o for artsiom should be linear, and this is ideal for me because I actually have thousands of nested lists within lists. — TTT, Nov 16 '12 at 10:45
Oh, wait nevermind. All of the solutions big o notation are n^n. — TTT, Nov 16 '12 at 10:56
@TTT: Depends how do you define N. If N = number of elements in all lists, then my solution is O(N^2) for Python <3.3, and O(N) for Python 3.3 thanks to `yield from`, which allows yielding straight to the top generator without going back through recursion. This can be done in linear time on Python <3.3 too, by smart use of iterators. — lqc, Nov 16 '12 at 16:28

lqc · Accepted Answer · 2012-11-16T16:34:16.763

The itertools documentation has some pretty good examples of iterating over lists and such, so it's always a good place to start when faced with such a task.

I would recomend using a generator, which avoid creating many levels of lists:

def flatten_all(iterable):
    for elem in iterable:
        if not isinstance(elem, list):
            yield elem
        else:
            for x in flatten_all(elem):
                yield x
            # in Python 3.3 just: yield from flatten_all(elem)

Application:

for x in flatten_all([1, [2, [3]]]):
    print(x)

# or if you need a list:
my_lst = list(flatten_all([1, [2, [3]]])
assert my_lst == [1, 2, 3]

Edit: Non-recursive linear version

def flatten_all(iterable):
    stack = [iter(iterable)]
    while stack:
        try:
            elem  = stack[-1].next()
            if not isinstance(elem, list):
                yield elem
            else:
                stack.append(iter(elem))
        except StopIteration:
            stack.pop()

I believe this is the right way to go. By looking at it i suppose it is just as fast as my solution. But it's also a lot more flexible because it's building a generator. — Niclas Nilsson, Nov 16 '12 at 10:46

Artsiom Rudzenka · Answer 2 · 2012-11-16T10:32:52.833

1

You can try something like this(code makes your list flat-in one row so you can print it later):

def make_flat(arr):
    res = []
    for l in arr:
        if isinstance(l, list):# or isinstance(l, collections.Iterable)
            res.extend(make_flat(l)) 
        else:
            res.append(l)
    return res

flat = make_flat(list1)
for x in flat:
    print x

Or:

def make_flat(arr):
    return sum(map(lambda a: make_flat(a) if isinstance(a,(list)) else [a],arr),[])

edited Nov 16 '12 at 10:32

answered Nov 16 '12 at 10:26

Artsiom Rudzenka

27,895
4
34
52

With that kind of big lists, I would time the different solutions... – Niclas Nilsson Nov 16 '12 at 10:59
Yes, right - tht's why i liked solution with yield, but it still doing what OP want's isn't it? It makes flatten list and printed it out. No one says that it should work for a big lists right? – Artsiom Rudzenka Nov 16 '12 at 12:05
Yeah! @TTT did a comment here that he then removed(?) And my comment was a response to that. It was in no way critic against your solution :) – Niclas Nilsson Nov 16 '12 at 12:09
@NiclasNilsson - oh)) i see) Peace))) – Artsiom Rudzenka Nov 16 '12 at 12:13

score 1 · Answer 3 · answered Nov 16 '12 at 10:27

1

This is an example using recursion:

list1 = [1, [2,3,4], [5, 6, 7, [8, 9]]]

def print_list(l):
    for e in l:
        if type(e) == list:
            print_list(e)
        else:
            print e

print_list(list1)

answered Nov 16 '12 at 10:27

Niclas Nilsson

5,691
3
30
43

Would you by any chance know the bigo notation for your recursion. If I'm seeing correctly it would be n^n assuming the len(list) = n. – TTT Nov 16 '12 at 10:49
1

I do believe a computer scientist would answer that better than this pastor having a lunch break ;) – Niclas Nilsson Nov 16 '12 at 10:56
As you say, it depends on how do you define "n". Otherwise traversing trees would be also n^n. But both for trees and for these lists (which look like trees, where data is in the leaves), it is considered to be linear since, usually, tree nodes are considered data elements (e.g. multibranch trees in databases, althought it's a bit more complicated, could be that n=d*log(d) where d is the actual data input (or # of keys) in the index). – Luis Masuelli Mar 30 '14 at 03:31

Python: multilevel nested lists

3 Answers3