Python nested loop miscounting instances of integers in list

Question

I'm banging my head against the wall trying to figure out why this nested loop is miscounting the number of times an integer occurs in a list. I've set up a function to take two lines of input, n and ar, where n is the number of integers in ar and ar is the list of integers. My code is below:

import sys

n = sys.stdin.readline()
n = int(n)
ar = sys.stdin.readline()
ar = ar.split(' ')
ar = [int(i) for i in ar]

def find_mode(n,ar):
    # create an empty dict and initially set count of all integers to 1
    d = {}
    for i in range(n):
        d[ar[i]] = 1

    for i in range(n):
        # hold integer i constant and check subsequent integers against it
        # increase count if match
        x = ar[i]

        for k in range(i+1,n):
            if ar[k] == x:
                d[ar[k]] += 1

    print(d)

The counter seems to be increasing the count by 1 every time, which leads me to believe it's a problem with the nested loop.

>>> 9 
>>> 1 2 3 4 4 9 9 0 0
{0: 2, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

OK

>>> 10
>>> 1 2 3 4 4 9 9 0 0 0
{0: 4, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

Count of 0 increased by +2

>>> 11
>>> 1 2 3 4 4 9 9 0 0 0 0
{0: 7, 1: 1, 2: 1, 3: 1, 4: 2, 9: 2}

Count of 0 increased by +3

I understand there might be more efficient or "pythonic" ways to count the amount of times a number occurs in a list but this was the solution I came up with and as someone still learning Python, it would help to understand why this exact solution is failing. Many thanks in advance.

You don't need to have a nested loop in order to solve this problem. The problem you're facing is the existence of a nested loop. — Austin A
– Austin A, Commented Mar 6, 2018 at 21:55
Can you elaborate a bit more as to why a nested loop won't work? My thought process was to hold one integer constant then loop through the rest of them (via nested loop) and compare them to the constant. Can this not be achieved? — Jon Behnken
– Jon Behnken, Commented Mar 6, 2018 at 22:00

a_guest · Accepted Answer · 2018-03-06 22:05:26Z

2

This is because for each distinct number in the list (call it x) you count the number of subsequent appearances. This is fine if a number only occurs twice but if it occurs multiple times you will over-count for each additional appearance.

For example: [0, 0, 0, 0]. You iterate over the list and then for each item you iterate over the list that follows that item. So for the first 0 you count a total of 3 subsequent 0s. For the second however you will count a total of 2 and for the third a total of 1 which makes 6. This is why you have 3 too much in the end.

You can achieve this task by using collections.Counter:

>>> from collections import Counter
>>> d = Counter(ar)

edited Mar 6, 2018 at 22:05

answered Mar 6, 2018 at 22:02

a_guest

36.7k15 gold badges75 silver badges137 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

TemporalWolf Over a year ago

This can be observed via adding print("Found %s at position %s" % (x, k)) to the inner loop where you increment the dct.

Jon Behnken Over a year ago

Thank you for the explanation. That hit the nail on the head for me.

mypetlion · Accepted Answer · 2018-03-06 21:54:01Z

0

I'm not exactly sure that I can fix your specific problem, but would something like this work instead?

d={}
for x in ar:
    d[x] = d.get(x, 0) + 1

I understand that you want to fix your existing work as a learning exercise, but I'm not sure that that approach is even the right one. As it is, I can't really tell what you're going for, so it's hard for me to offer specific advice. I would recommend that you don't throw good time after bad.

answered Mar 6, 2018 at 21:54

mypetlion

2,5445 gold badges21 silver badges22 bronze badges

Comments

Adi219 · Accepted Answer · 2018-03-06 22:01:18Z

0

python has a method to do exactly what you're describing.

It's called .count().

If you do ar.count(3), it will return the number of occurences of 3 in the list ar.

** In your case:**

There's no need for a nested loop as you only need one loop.

Try this:

dic = {}
for num in ar:
    if num not in dic:
        dic[num] = 1
    else:
        dic[num] += 1

This would produce the dict you want with the numbers and their occurences

answered Mar 6, 2018 at 22:01

Adi219

4,8362 gold badges22 silver badges44 bronze badges

Comments

Austin A · Accepted Answer · 2018-03-06 22:07:47Z

0

You can refer to other answers as to how you should solve this problem more efficiently, but to answer the question you're asking (Why doesn't this nested loop work?):

To visualize what your nested loop is doing consider the following input:

0 0 0 0 0

Your algorithm will count the following:

0 0 0 0 0 ^ ^ ^ ^ ^ (5)

then,

0 0 0 0 0 ^ ^ ^ ^ (4)

then,

0 0 0 0 0 ^ ^ ^ (3)

then,

0 0 0 0 0 ^ ^ (2)

and finally,

0 0 0 0 0 ^ (1)

What happens is it counts the number of 0's multiple times over. In this instance it will count

15 0's (5+4+3+2+1)

answered Mar 6, 2018 at 22:07

Austin A

5662 silver badges16 bronze badges

2 Comments

Jon Behnken Over a year ago

Thank you very much for this explanation. Essentially, the first pass is the correct answer, which is why it was recommended not to use a nested loop?

Austin A Over a year ago

Yeah, that's exactly why

Goran B. · Accepted Answer · 2018-03-06 22:18:21Z

0

itertools are your friend

from itertools import groupby

def group_by_kv_l(n):
    l = []
    for k, v in groupby(n):
        l.append((len(list(v)),int(k)))
    return l

def group_by_kv_d(n):
    d = {}
    for k, v in groupby(n):
        d[(int(k))] = len(list(v))
    return d

if __name__ == "__main__":

    n = input().split()
    n = "".join(n)

    print(
        "STDIN: {}".format(n)
    )

    print(
        group_by_kv_l(n)
    )

    print(
        group_by_kv_d(n)
    )

answered Mar 6, 2018 at 22:18

Goran B.

5884 silver badges14 bronze badges

Collectives™ on Stack Overflow

Python nested loop miscounting instances of integers in list

5 Answers 5

2 Comments

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related