An ALGORITHM to create one list from "X" nested lists in Python

Question

What is the simplest way to create this list in Python?

First, suppose I have this nested list:

oldList = [ [{'letter':'a'}], [{'letter':'b'}], [{'letter':'c'}] ]

I want a function to spit out:

newList = [ {'letter':a}, {'letter':'b'}, {'letter':'c'} ]

Well, this could be done manually. However, what if there are three nested? ...X nested

Tricky? :)

Not tricky. Duplicate: http://stackoverflow.com/questions/716477/join-list-of-lists-in-python, which is itself a duplicate of other questions. — S.Lott, Oct 06 '09 at 10:51
Duplicate of this, also: http://stackoverflow.com/questions/1077015/python-list-comprehensions-compressing-a-list-of-lists — S.Lott, Oct 06 '09 at 10:52

score 4 · Answer 1 · answered Oct 06 '09 at 05:20

4

Recursive solutions are simplest, but limited to at most a few thousand levels of nesting before you get an exception about too-deep recursion. For real generality, you can eliminate recursion by keeping your own stack; iterators are good things to keep on said stack, and the whole function's best written as a generator (just call list(flatten(thelist)) if you really want a huge list result).

def flatten(alist):
  stack = [iter(alist)]
  while stack:
    current = stack.pop()
    for item in current:
      if isinstance(item, list):
        stack.append(current)
        stack.append(iter(item))
        break
      yield item

Now this should let you handle as many levels of nesting as you have virtual memory for;-).

answered Oct 06 '09 at 05:20

Alex Martelli

854,459
170
1,222
1,395

you can also increase the recursion limit with sys.setrecursionlimit – John La Rooy Oct 06 '09 at 05:27
@Alex: glad to see you here. Sorry for a bit of meta, here, is my response re. copyrights etc? (BTW great non-recursive sol') – mjv Oct 06 '09 at 05:30
@gnibbler, only up to a limit, NOT without bounds. @mjv, by posting a link to a google books snippet you're most certainly in the clear (not sure how O'Reilly feels about republication in other public fora such as this one). – Alex Martelli Oct 06 '09 at 05:33
@Alex M Thanks for the hint. Hopefully the publisher would see it as free advertisement. 'nough on this, back to coding... – mjv Oct 06 '09 at 05:47

Jimmy · Accepted Answer · 2009-10-06T05:27:12.430

2

http://www.daniel-lemire.com/blog/archives/2006/05/10/flattening-lists-in-python/

from that link (with a couple minor changes:

def flatten(l):
  if isinstance(l, list):
     return sum(map(flatten,l),[])
  else:
     return [l]

edited Oct 06 '09 at 05:27

answered Oct 06 '09 at 05:07

Jimmy

89,068
17
119
137

1

Way too broad: a dict also has an `__iter__`, for example, yet the OP's example makes it totally clear that he does NOT want to "flatten" dicts, only lists! – Alex Martelli Oct 06 '09 at 05:22
:) good point. that was an unnecessary edit by me from the original. (the other edit being the second parameter on sum) – Jimmy Oct 06 '09 at 05:25
A side note: PEP 8 encourages not to use lowercase L as an identifier. This makes the code less legible, because `l` (L) looks like `1` (one). – Eric O. Lebigot Oct 06 '09 at 07:10

score 1 · Answer 3 · answered Oct 06 '09 at 11:06

1

The simplest answer is this

Only you can prevent nested lists

Do not create a list of lists using append. Create a flat list using extend.

answered Oct 06 '09 at 11:06

S.Lott

384,516
81
508
779

mjv · Answer 4 · 2009-10-06T05:27:29.513

0

The Python Cookbook Martelli, Ravenscroft and Asher 2005 O'Reilley also offers a solution to this flattening problem.
See 4.6 Flattening a nested sequence.
This solution uses generators which can be a good thing if the lists are long.
Also, this solution deals equaly well with lists or tuples.

Note: Oops... I rushed a bit. I'm unsure of the legality of reproducing this snippet here... let me look for policy / precedents in this area.

Edit: later found reference as a Google Books preview.

Here's a link to this section of the book in Google books

edited Oct 06 '09 at 05:27

answered Oct 06 '09 at 05:15

mjv

73,152
14
113
156

As a co-author of that recipe (yep, Luther Blissett, c'est moi!-), I know think the last, most advanced, recursion-removal recipe is a tad too fancy -- the version I wrote (from scratch, no copying) in my answer above is slightly less optimized (does a bit more pop/append pairs than strictly needed... but they're cheap operations!), but, IMHO, easier to follow (no `else` branches, while the printed version has two;-). – Alex Martelli Oct 06 '09 at 05:28

score 0 · Answer 5 · answered Oct 06 '09 at 06:51

0

I prefer Alex Martelli's post as usual. Just want to add a not recommended trick:

from Tkinter import _flatten
print _flatten(oldList)

answered Oct 06 '09 at 06:51

sunqiang

6,422
1
32
32

An ALGORITHM to create one list from "X" nested lists in Python

5 Answers5