Flattening a list recursively

Question

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

I am having trouble using python to recursively flatten a list. I have seen a number of methods that require list comprehension and various methods requiring imports however I am looking for a very basic method to recursively flatten a list of varying depth that does not use any for loops either. I had a series of test however there are two I cannot pass

flatten([[[[]]], [], [[]], [[], []]]) # empty multidimensional list
flatten([[1], [2, 3], [4, [5, [6, [7, [8]]]]]]) # multiple nested list

My code

def flatten(test_list):
    #define base case to exit recursive method
    if len(test_list) == 0:
       return []
    elif isinstance(test_list,list) and type(test_list[0]) in [int,str]:
        return [test_list[0]] + flatten(test_list[1:])
    elif isinstance(test_list,list) and isinstance(test_list[0],list):
        return test_list[0] + flatten(test_list[1:])
    else:
        return flatten(test_list[1:])

I would appreciate some advice.

possible diplicate http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python — root, Sep 18 '12 at 07:34
@ Anthony -- check out the supposed duplicate. I think your questions has been answered well. — root, Sep 18 '12 at 07:37
I asked a similar question [here](http://stackoverflow.com/questions/9372463/extracting-strings-from-nested-lists-in-python), and the answer given doesn't use any imports or comprehensions. It does have a for loop though. Any particularly reason for that requirement? — Marius, Sep 18 '12 at 07:38

score 41 · Answer 1 · answered Sep 18 '12 at 07:48

41

This handles both of your cases, and I think will solve the general case, without any for loops:

def flatten(S):
    if S == []:
        return S
    if isinstance(S[0], list):
        return flatten(S[0]) + flatten(S[1:])
    return S[:1] + flatten(S[1:])

answered Sep 18 '12 at 07:48

Mu Mind

10,460
4
34
67

Thank you @Mu Mind - this is exactly what I was missing - returning the first part of the list to the recursive function as well as the remaining part. Been doing my head in so thanks heaps – Anthony Gough Sep 18 '12 at 09:08
I think the first if clause should be: if S == [] or len(S) == 1, since if then length is 1 the second or third return wich concats with S[1:] will throw an Index out of range.... – Robin van Leeuwen Jan 11 '17 at 13:07
1

@RvL Try it. =) Slicing `[:1]` and `[1:]` are perfectly reasonable for single-item lists, and anyway slicing never raises IndexError. – Mu Mind Jan 12 '17 at 01:43

score 23 · Answer 2 · answered Sep 18 '12 at 09:34

23

li=[[1,[[2]],[[[3]]]],[['4'],{5:5}]]
flatten=lambda l: sum(map(flatten,l),[]) if isinstance(l,list) else [l]
print flatten(li)

answered Sep 18 '12 at 09:34

chyanog

537
4
13

What's the purpose of `sum`? – Tom Hale Dec 15 '17 at 12:20
1

@TomHale `sum(list, list)` concatenates them(lists). – plhn Dec 26 '18 at 06:33

score 7 · Answer 3 · answered Sep 18 '12 at 07:41

7

Here's a possible solution without any loops or list comprehensions, just using recursion:

def flatten(test_list):
    if isinstance(test_list, list):
        if len(test_list) == 0:
            return []
        first, rest = test_list[0], test_list[1:]
        return flatten(first) + flatten(rest)
    else:
        return [test_list]

answered Sep 18 '12 at 07:41

tobias_k

78,071
11
109
168

1

Mmm, tastes like Lisp. This is literally the same code we'd have written in Scheme back in the day... – nneonneo Sep 18 '12 at 07:44
1

This will also return `[0]` for `flatten(0)`. Not sure if that's a pro or a con... – Mu Mind Sep 18 '12 at 07:52
2

This is a good answer given the requirements in the question (no loops), but it's probably worth noting that performance will be pretty lousy. Python's `list` type is not a linked list, but rather something array-like. Each time you join two lists in the recursive step `flatten(first) + flatten(rest)`, the code will copy all the contents of both lists. I think will take O(N^2) time to produce a length N output list. – Blckknght Sep 18 '12 at 07:53
@tobias_k Thank you for helping me - I knew from debugging the code where it was failing however I never thought to return the first part of the list as a parameter to the recursive function `return flatten(test_list[0]) + flatten(test_list[1:])` I was failing when test_list was `[[4, [5, [6, [7, [8]]]]]]` but could not work out the next step. I understand how inefficient recursion can be however this was an exercise in recursion. I would not have done it this way otherwise. Thanks heaps – Anthony Gough Sep 18 '12 at 08:59
In Python3, the code would be ```def flatten1(test_list): if isinstance(test_list, list): if len(test_list) == 0: return [] first, rest = test_list[0], test_list[1:] return chain(flatten(first),flatten(rest)) else: return [test_list]``` – soumya-kole Oct 23 '21 at 03:26

score 7 · Answer 4 · answered Sep 18 '12 at 07:59

7

Well, if you want it a lisp way, let's have it.

atom = lambda x: not isinstance(x, list)
nil  = lambda x: not x
car  = lambda x: x[0]
cdr  = lambda x: x[1:]
cons = lambda x, y: x + y

flatten = lambda x: [x] if atom(x) else x if nil(x) else cons(*map(flatten, [car(x), cdr(x)]))

answered Sep 18 '12 at 07:59

georg

204,715
48
286
369

3

lol, I love how you changed the last bit from `flatten(x[0]) + flatten(x[1:])` to `cons(*map(flatten, [car(x), cdr(x)]))`. Could you add some more parentheses for old times' sake? – Mu Mind Sep 18 '12 at 08:05

Flattening a list recursively

4 Answers4

Linked

Related