1

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.

4
  • 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, 2012 at 10:45
  • Great. Accept the answer you end up using :) Nov 16, 2012 at 10:47
  • Oh, wait nevermind. All of the solutions big o notation are n^n.
    – TTT
    Nov 16, 2012 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, 2012 at 16:28

3 Answers 3

4

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()
1
  • 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. Nov 16, 2012 at 10:46
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)
3
  • 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, 2012 at 10:49
  • 1
    I do believe a computer scientist would answer that better than this pastor having a lunch break ;) Nov 16, 2012 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). Mar 30, 2014 at 3:31
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),[])
4
  • With that kind of big lists, I would time the different solutions... Nov 16, 2012 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? Nov 16, 2012 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 :) Nov 16, 2012 at 12:09
  • @NiclasNilsson - oh)) i see) Peace))) Nov 16, 2012 at 12:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.