CODEWITHSUNDEEP
pythonpython-3.xlistfor-looprecursion
Amy
Amy

Reputation: 1

How do I recursively flatten a nested list of loops with outer lists first?

For example, given a list like [[[1]]],[2,3,4],5,[[6]],7], the output should not be [1,2,3,4,5,6,7], but should instead be [5,7,2,3,4,6,1].

Here is what I have now:

def foo (intlist, result):
    for item in intlist:
        if (type(item) == int):
            result.append(item)
            intlist.remove(item)
        else:
            --------- 
    for item in intlist:
        foo(intlist, result)
    return result

I am not sure how to verify if the list only contains lists and no ints on the side for the else statement.

Upvotes: 0

Views: 140

Answers (3)

Mike67
Mike67

Reputation: 11342

A slightly different approach. Here, the lists are concatenated then passed to the next level.

lst = [[[[1]]],[2,3,4],5,[[6]],7]

def foo (intlist, result):
    tmp = []
    for item in intlist:
        if (type(item) == list):
            tmp.extend(item)  # pass list to next level
        else:
            result.append(item)  # add item to result
    if len(tmp): 
        foo(tmp, result) # go to next level
    return result

result = foo(lst, [])
print(result)  # [5,7,2,3,4,6,1]

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

You can make this recursive, so that each depth of recursion unpacks the corresponding depth list.

def foo(intlist, result):
    if not intlist:
        return
    temp = []
    for item in intlist:
        if type(item) != list:
            result.append(item)
        else:
            for i in item:
                temp.append(i)
    intlist = temp
    foo(intlist, result)

your_list = []
result = []
foo(your_list, result)
print(result)   # outputs [5, 7, 2, 3, 4, 1, 6]

Upvotes: 1

Mulan
Mulan

Reputation: 135237

I think it's a nice use-case for python's wonderful generators -

def preorder (ls):
  if not ls:
    return
  elif isinstance(ls[0], list):
    yield from preorder(ls[1:] + ls[0])
  else:
    yield ls[0]
    yield from preorder(ls[1:])

input = [[[[1]]],[2,3,4],5,[[6]],7]
result = list(preorder(input))
print(result)
# [5, 7, 2, 3, 4, 6, 1]

Here's what the evaluation looks like -

[[[[1]]],[2,3,4],5,[[6]],7]
[[2,3,4],5,[[6]],7] + [[[1]]]
[[2,3,4],5,[[6]],7,[[1]]]
[5,[[6]],7,[[1]]] + [2,3,4]
[5,[[6]],7,[[1]],2,3,4]
5                                # yield
[[[6]],7,[[1]],2,3,4]
[7,[[1]],2,3,4] + [[6]]
[7,[[1]],2,3,4,[6]]
7                                # yield
[[[1]],2,3,4,[6]]
[2,3,4,[6]] + [[1]]
[2,3,4,[6],[1]]
2                                # yield
3                                # yield
4                                # yield
[[6],[1]]
[[1]] + [6]
[[1],6]
[6] + [1]
[6,1]
6                                # yield
1                                # yield

Or you can eagerly compute the result using the same logical recursion structure -

def preorder (ls):
  if not ls:
    return []
  elif isinstance(ls[0], list):
    return preorder(ls[1:] + ls[0])
  else:
    return [ ls[0], *preorder(ls[1:]) ]

input = [[[[1]]],[2,3,4],5,[[6]],7]
result = preorder(input)
print(result)
# [5, 7, 2, 3, 4, 6, 1]

Upvotes: 1

Related Questions