Retrieving the length of a list after flattening

Question

I've seen a few questions asking about list flattening and I was wondering how to retrieve the length of the flattened list without actually flattening it. My list can be arbitrarily deep.

Case 1:

Input:

[[[1, 2], 3], 4]

Output:

Case 2:

Input:

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

Output:

Here's a recursive implementation:

def flattenlen(a):
    total = 0
    for i in range(len(a)):
        if type(a[i]) == list:
            total += flattenlen(a[i])
        else:
            total += 1
    return total

print flattenlen([[[[1, 2], [3, 4]], 5], [6, 7]])

Output:

Does anyone have a closed form solution? Is there a built-in method or a library to achieve this? Is there a more efficient method that I have missed?

i've yet to encounter a list-flattening problem that couldn't be solved by just not having arbitrarily nested lists in the first place :) — Eevee, Jun 29 '14 at 20:52
http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python just add `len()` to one of those recipes — motoku, Jun 29 '14 at 21:40

Martijn Pieters · Accepted Answer · 2014-06-29T21:20:52.200

You can easily do this without building separate lists:

def flattenlen(a):
    return sum(flattenlen(i) if isinstance(i, list) else 1 for i in a)

This sums up the results of recursive calls for lists, individual 1 values for the rest, all in one generator expression loop.

For a non-recursive version, use a stack:

def flattenlen(a):
    total = 0
    stack = [a]
    while stack:
        lst = stack.pop()
        for i in lst:
            if isinstance(i, list):
                stack.append(i)
            else:
                total += 1
    return total

For a more complete solution, use collections.Iterable and basestring to test for any iterable object that is not a string (unicode or str):

from collections import Iterable

_typetest = lambda t: isinstance(t, Iterable) and not isinstance(t, basestring)

def flattenlen(a):
    return sum(flattenlen(i) if _typetest(i) else 1 for i in a)

Demo:

>>> from collections import Iterable
>>> _typetest = lambda t: isinstance(t, Iterable) and not isinstance(t, basestring)
>>> def flattenlen(a):
...     return sum(flattenlen(i) if _typetest(i) else 1 for i in a)
... 
>>> flattenlen([[[[1, 2], [3, 4]], 5], [6, 7]])
7
>>> flattenlen([([[1, 2], [3, 4]], 5), {6, 7, 'foobar'}])
8

Beat me... except I was going to use `collections.Iterable` instead of `list` — Jon Clements, Jun 29 '14 at 20:53

Retrieving the length of a list after flattening

Case 1:

Case 2:

1 Answers1