Regarding double loop in Python

Question

I need help to fix this "index out of range" problem in this double for loop code I have.

aList = ["G", "D", "A", "G", "A", "B"]

for i in range(0, len(aList)-1):
    for j in range(i+1, len(aList)):
        if aList[i] == aList[j]:
            removeThis = aList[i]
            aList.remove(removeThis)

Basically I want to get the first non-repeating string in aList, which is supposed to be D in this case. Thank you in advance!

( edit ) : I saw many help given by using built-in Python functions, but I'm trying to do this code without built-in functions for learning purposes.

Does this answer your question? [Removing from a list while iterating over it](https://stackoverflow.com/questions/6500888/removing-from-a-list-while-iterating-over-it) — MisterMiyagi, Apr 01 '20 at 08:26
Does this answer your question? [strange result when removing item from a list](https://stackoverflow.com/questions/6260089/strange-result-when-removing-item-from-a-list) — Jongware, Apr 01 '20 at 08:27

Thierry Lathuille · Answer 1 · 2020-04-01T08:42:20.217

A more efficient solution, in O(n): we iterate once on the list to get the counts (actually, we keep the list of indices, so we also have the first one).

Then, we keep the first of the ones who appeared only once.

A first solution, for latest versions of Python with ordered dicts (guaranteed since 3.7):

def first_unique(aList):
    seen = {}

    for index, value in enumerate(aList):
        seen.setdefault(value, []).append(index)

    for value, indices in seen.items():
        if len(indices)==1:  
            # as the dict is ordered, the first unique value we encounter
            # while iterating on the dict was the first one in the list
            return value

aList = ["G", "D", "A", "G", "A", "B"]         
print(first_unique(aList))
#'D'

For older versions of Python without ordered dict, we can filter the unique values, and keep the one with the smallest first index:

def first_unique_older_python(aList):
    seen = {}

    for index, value in enumerate(aList):
        seen.setdefault(value, []).append(index)

    uniques = ((indices[0], value) for value, indices in seen.items() if len(indices)==1)
    return min(uniques)[1]


aList = ["G", "D", "A", "G", "A", "B"]        


print(first_unique_older_python(aList))
#'D'

score 1 · Answer 2 · answered Apr 01 '20 at 08:13

1

You can't remove an item from a list while you're iterating over it, it will break the iteration. If you only want the first non repeating string, as you say in your question, then you're OK because you can break out of the loop immediately which doesn't give a chance for the iterations to notice that the list has changed:

def remove_first_dupe(aList):
    for i in range(0, len(aList)-1):
        for j in range(i+1, len(aList)):
            if aList[i] == aList[j]:
                removeThis = aList[i]
                aList.remove(removeThis)
                return   # Added this

I put it into a function to make it easy to break out of both loops at once, using the return statement.

answered Apr 01 '20 at 08:13

Arthur Tacca

8,833
2
31
49

Thank you for your response! The code give me a "list index out of range" though, how should I fix this error? – Eli Apr 01 '20 at 08:40
@Eli I just tried my function with your example list and it does not give an error. Did you mean my function or yours? The way to fix your function is to escape from the iteration somehow, like adding `return` as I showed in my answer. – Arthur Tacca Apr 01 '20 at 09:26

XPhyro · Answer 3 · 2020-04-01T08:37:15.117

0

As @Arthur Tacca stated in their answer, you cannot remove an item from a list while iterating over it, as that will change the indices of the list and shorten the list you're getting an index error.

I would suggest a more concise, but SLOW way to do it, taking advantage of the built-in python functions:

aList = ["G", "D", "A", "G", "A", "B"]

counts = [aList.count(i) for i in aList]
first_non_repeating = aList[counts.index(min(counts))]

edited Apr 01 '20 at 08:37

answered Apr 01 '20 at 08:20

XPhyro

419
1
6
16

``counts`` needlessly uses an O(n^2) algorithm, and ``first_non_repeating `` needlessly an O(n) algorithm. Please have a look at ``collections.Counter``. – MisterMiyagi Apr 01 '20 at 08:34
@MisterMiyagi Thanks for pointing it out, I'll have a look. I have edited my answer to be verbose about the speed. – XPhyro Apr 01 '20 at 08:38

Lior Pollak · Answer 4 · 2020-04-01T08:39:59.803

-1

You can do this using reduce:

>>> aList = ["G", "D", "A", "G", "A", "B"]
>>> b = [alist[0]]
>>> reduce(lambda x,y: y not in b and b.append(y), aList)
>>> b
['D', 'A', 'G', 'B']
>>> b[0]
'D'

Note that the reduce here puts in b every non repeating element of aList in order, so the first element of b would be the first non-repeating string in aList.

edited Apr 01 '20 at 08:39

answered Apr 01 '20 at 08:17

Lior Pollak

3,362
5
27
48

This algorithm doesn't work. Since the lambda discards ``x``, the first element of ``aList`` is ignored unconditionally. It will fail by always picking the second element of ``aList``. Try ``aList = ["G", "G", "D", "A", "G", "A", "B"]`` for example. – MisterMiyagi Apr 01 '20 at 08:39
The recent change only cause the first element to be always picked, instead of the second. It still does not respect the count of items at all. – MisterMiyagi Apr 01 '20 at 08:42

Regarding double loop in Python

4 Answers4