0

Given a Python list whose elements are either integers or lists of integers (only we don't know how deep the nesting goes), how can we find the sum of each individual integer within the list?

It's fairly straightforward to find the sum of a list whose nesting only goes one level deep, e.g.

[1, [1, 2, 3]]
# sum is 7

But what if the nesting goes two, three, or more levels deep?

[1, [1, [2, 3]]]
# two levels deep

[1, [1, [2, [3]]]]
# three levels deep

The sum in each of the above cases is the same (i.e. 7). I think the best approach is using recursion where the base case is a list with a single integer element, but beyond that I'm stuck.

Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
djlovesupr3me
  • 79
  • 2
  • 8

4 Answers4

7

You can use this recursive solution:

from collections import Iterable
def flatten(collection):
  for element in collection:
    if isinstance(element, Iterable):
      for x in flatten(element):
        yield x
    else:
      yield element

Demo:

>>> lis = [1, [1, [2, [3]]]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, 2, 3]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, [2, 3]]]
>>> sum(flatten(lis))
7
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
5

Easiest way I can think of:

from compiler.ast import flatten
sum(flatten(numbs))
Captain Skyhawk
  • 3,499
  • 2
  • 25
  • 39
4

Assuming that you are only using lists, this should do the trick:

def sum_nested(l):
    s = 0
    for item in l:
        if type(item) is list:
            s += sum_nested(item)
        else:
            s += item
    return s
Blair
  • 6,623
  • 1
  • 36
  • 42
  • This one is good because it avoids unnecessary allocations that occur when using `flatten` (in any of the suggested forms). I would change `==` to `is` in the type test though. – Alexei Sholik Jul 01 '13 at 18:41
  • In the real world, though, `sum(flatten(x))` will likely be more performant if `flatten` produces an iterable. – Alexei Sholik Jul 01 '13 at 18:44
  • The [PEP Style guide](http://www.python.org/dev/peps/pep-0008/#programming-recommendations) suggests using isinstance(item, list) for all object comparisons. "Object type comparisons should always use isinstance() instead of comparing types directly." Otherwise nice answer. – Dan Jul 01 '13 at 19:58
  • 1
    @android The `flatten` implementation in my answer (as well as Ashwini's) ought not to allocate anything unnecessarily, save for a generator object for a brief period of time (on my system, this is only 80 bytes). @Brien However, I ran your solution through `timeit` with `[1, [1, [2, [3]]]]` (default number of runs) as well as mine and Ashwini's... yours: `2.8680150508880615`; mine: `16.686115026474`; Ashwini's: `14.88997197151184`. Captain Skyhawk's was pretty good as well, for being deprecated: `5.101460933685303`. Yours with `isinstance` instead was `3.312623977661133`. You get my upvote. – 2rs2ts Jul 01 '13 at 20:42
  • Ah, the reason why our solutions are so slow is the fact that we are using `isinstance(item, Iterable)`. When I change it to `isinstance(item, list)` I get `3.9191691875457764`. The only-lists assumption is a good optimization. – 2rs2ts Jul 01 '13 at 20:47
2

One approach: flatten the list, then use sum().

from collections import Iterable
def flatten(lst):
    for i in lst:
        if isinstance(i, Iterable) and not isinstance(i, basestring):
            for sublst in flatten(i):
                yield sublst
        else:
            yield i

sum(flatten([1, [1, [2, [3]]]]))

If you are dealing only with lists, change isinstance(i, Iterable) to isinstance(i, list) for a massive performance boost.

Note that the basestring check is not necessary when using sum() as Ashwini pointed out.

Community
  • 1
  • 1
2rs2ts
  • 10,662
  • 10
  • 51
  • 95