CODEWITHSUNDEEP
pythonlistrecursion
taylorSeries
taylorSeries

Reputation: 492

Deep list count - count lists within lists

I am trying to get the length of a list, but that list can contain other lists that are deeply nested (e.g. [[[[[[[]]]]]]]).

But you have to get any non list elements in the count as well: [1, 2, [3, 4]] would output 5 (1, 2, 3, 4 and a list). ["a", "b", ["c", "d", ["e"]]] would output 7.

It first comes to mind to use recursion to solve this problem. I wrote this:

def deep_count(arr, count=0):
    if any(type(i) == list for i in arr):
        for i in arr:
            if type(i) == list:
                count += len(arr)
            else:
                count += 1
        return deep_count(arr[1:], count)
    return count

It's outputting 9 instead of 7. And if it's just nested lists like [[[]]] it only outputs 1.

Upvotes: 2

Views: 213

Answers (6)

MusicalNinja
MusicalNinja

Reputation: 182

A twoline answer would be:

def lenrecursive(seq):
    return len(seq) + sum(lenrecursive(s) for s in seq if isinstance(s,Sized) and not isinstance(s, str))

However this will not take into account that other things may have a len

A more complete handling using EAPF approach is:

def lenrecursive(seq):
    """
    Returns total summed length of all elements recursively.
    If no elements support len then return will be 0, no TypeError will be raised
    """
    def _len(x):
        try:
            return len(x)
        except TypeError: #no len
            return 0
    
    try:
        return _len(seq) + sum(lenrecursive(s) for s in seq if not isinstance(s, str))
    except TypeError: #not iterable
        return _len(seq)

Notes:

  1. Why not isinstance(s, str)? - Strings will lead to infinite recursion as a one-character string is a sequence so lenrecursive(a) would return 1 + lenrecursive(a) which is 1 + 1 + lenrecursive(a) which is 1 + 1 + 1 + ...
  2. Why EAFP using try: except: rather than LBYL checking with isinstance? - because there are so many things out there that support len and you don't know whether the next time you call this you've created a custom class which has a __len__ but doesn't subclass Sequence, Mapping, or something else that inherits from collections.Sized

Upvotes: 1

Jab
Jab

Reputation: 27515

There doesn't seem to be a need for supplying an initial value, you can just use arr as the only parameter, then just get the count and if the current element is a list then also add that list's count.

def f(arr):
    count = len(arr)
    for element in arr:
        if isinstance(element, list):
            count += f(element)
    return count

>>> f([1, 2, [3, 4]])
5
>>> f(["a", "b", ["c", "d", ["e"]]])
7

Upvotes: 4

Kelly Bundy
Kelly Bundy

Reputation: 27660

Recursively adding all the list lengths (Try it online!):

def f(xs):
    return len(xs) + sum(f(x) for x in xs
                         if isinstance(x, list))

A variation (Try it online!):

def f(xs):
    return isinstance(xs, list) and len(xs) + sum(map(f, xs))

Upvotes: 4

Mechanic Pig
Mechanic Pig

Reputation: 7751

My old answer takes the result of the last example of OP as the expected output. If it is not considered, the answer is very simple:

>>> def count_deep_list(lst):
...     return sum(count_deep_list(val) for val in lst if isinstance(val, list)) + len(lst)
...
>>> count_deep_list([1, 2, [3, 4]])
5
>>> count_deep_list(["a", "b", ["c", "d", ["e"]]])
7
>>> count_deep_list([[[]]])
2

Old Answer:

It seems that you need a special judgment on the internal empty list and the incoming list itself. I think it needs to be implemented with the help of closure:

>>> def count_deep_list(lst):
...     def count(_lst):
...         if isinstance(_lst, list):
...             if not _lst:
...                 return 0
...             else:
...                 return sum(map(count, _lst)) + 1
...         else:
...             return 1
...
...     return count(lst) - 1 if lst else 0
...
>>> count_deep_list([1, 2, [3, 4]])
5
>>> count_deep_list(["a", "b", ["c", "d", ["e"]]])
7
>>> count_deep_list([[[]]])
1

Simpler implementation:

>>> def count_deep_list(lst):
...     def count(_lst):
...         return sum(count(val) if val else -1 for val in _lst if isinstance(val, list)) + len(_lst)

...     return count(lst) if lst else 0
...
>>> count_deep_list([1, 2, [3, 4]])
5
>>> count_deep_list(["a", "b", ["c", "d", ["e"]]])
7
>>> count_deep_list([[[]]])
1

Upvotes: 1

John Brown
John Brown

Reputation: 123

class Counter:
def __init__(self):
    self.counter = 0

def count_elements(self, l):
    for el in l:
        if type(el) == list:
            self.counter += 1
            self.count_elements(el)
        else:
            self.counter += 1

l = ["a", "b", ["c", "d", ["e"]]]

c = Counter()
c.count_elements(l)
print(c.counter)

Upvotes: -1

jkoestinger
jkoestinger

Reputation: 1010

When talking recursion, always think of the base case (which case would not make a recursion). In your problem, it would be when the list is empty, then it would return a count of 0.

So you could start implementing it like so:

def f(arr):
    if arr == []:
        return 0

For the rest of the implementation, you have two approaches:

  • Looping over the list and add f(sublist) to the count when it is effectively a sublist, and add 1 when it isn't
  • Go full recursion and always call the f(x) function, no matter if it is a sublist or not, and always add the result to the count. In this case, you have a new base case where f(not_a_list) would return 1

I think this should unstuck you

Note: I just read that recursion is not required, you came up with it. I think this is a good approach for this kind of problem

Upvotes: 2

Related Questions