How to fix 'IndexError: list index out of range' using 'for in range:' while recursion

Question

I'm trying to implement 'unique_in_order' function. This function takes as argument a sequence and returns a list of items without any elements with the same value next to each other and preserving the original order of elements.

For example:

unique_in_order('AAAABBBCCDAABBB') == ['A', 'B', 'C', 'D', 'A', 'B']
unique_in_order('ABBCcAD')         == ['A', 'B', 'C', 'c', 'A', 'D']
unique_in_order([1,2,2,3,3])       == [1,2,3]
ets

It's the code of this function:

def unique_in_order(iterable):
    iterable = list(iterable)
    l_lenth = int(len(iterable))
    for i in range(0, l_lenth-1):
        if iterable[i] == iterable[i+1]:
            del iterable[i+1]
            l_lenth = l_lenth - 1
            unique_in_order(iterable)
    return(iterable)`

But if we will run this, an error occurres:

    Traceback (most recent call last):
      File "test.py", line 15, in <module>
        unique_in_order(x)
      File "test.py", line 11, in unique_in_order
        unique_in_order(iterable)
      File "test.py", line 11, in unique_in_order
        unique_in_order(iterable)
      File "test.py", line 11, in unique_in_order
        unique_in_order(iterable)
      [Previous line repeated 4 more times]
      File "test.py", line 6, in unique_in_order
        if iterable[i] == iterable[i+1]:
    IndexError: list index out of range

I tried to add some 'print()' to monitor the progress:

def unique_in_order(iterable):
    iterable = list(iterable)
    l_lenth = int(len(iterable))
    for i in range(0, l_lenth-1):
        if iterable[i] == iterable[i+1]:
            del iterable[i+1]
            l_lenth = l_lenth - 1
            print('sign {0} was deleted \n new list: \n{1}'.format(i+1, iterable))
            print('new lenth: {0}, i = {1}'.format(l_lenth,i))
            unique_in_order(iterable)
    print('Result: {}'.format(iterable))
x = 'AAABBBCCDAA'
print('input data: {0}\nlenth: {1}'.format(x,len(x)))
unique_in_order(x)

result:

input data: AAABBBCCDAA
lenth: 11
sign 1 was deleted
 new list:
['A', 'A', 'B', 'B', 'B', 'C', 'C', 'D', 'A', 'A']
new lenth: 10, i = 0
sign 1 was deleted
 new list:
['A', 'B', 'B', 'B', 'C', 'C', 'D', 'A', 'A']
new lenth: 9, i = 0
sign 2 was deleted
 new list:
['A', 'B', 'B', 'C', 'C', 'D', 'A', 'A']
new lenth: 8, i = 1
sign 2 was deleted
 new list:
['A', 'B', 'C', 'C', 'D', 'A', 'A']
new lenth: 7, i = 1
sign 3 was deleted
 new list:
['A', 'B', 'C', 'D', 'A', 'A']
new lenth: 6, i = 2
sign 5 was deleted
 new list:
['A', 'B', 'C', 'D', 'A']
new lenth: 5, i = 4
Result: ['A', 'B', 'C', 'D', 'A']
Result: ['A', 'B', 'C', 'D', 'A']
sign 5 was deleted
 new list:
['A', 'B', 'C', 'D', 'A']
new lenth: 5, i = 4
Result: ['A', 'B', 'C', 'D', 'A']
Traceback (most recent call last):
  File "test.py", line 16, in <module>
    unique_in_order(x)
  File "test.py", line 11, in unique_in_order
    unique_in_order(iterable)
  File "test.py", line 11, in unique_in_order
    unique_in_order(iterable)
  File "test.py", line 11, in unique_in_order
    unique_in_order(iterable)
  [Previous line repeated 1 more time]
  File "test.py", line 6, in unique_in_order
    if iterable[i] == iterable[i+1]:
IndexError: list index out of range

So, as we can see, the result is right, but because of 'IndexError' I can't return() the output data. Additionally, the 'Result:' line is displayed two more times when i = 4(I guess in this step this problem occures). I would be grateful if you will help me to solve this problem. Thanks in advance.

DetectivePikachu · Accepted Answer · 2019-09-06 20:23:50Z

You're going to get some pretty wacky behavior trying to delete from a list as you are iterating through it. And I don't understand why you are recursively calling this function, you're already iterating through the entire list with a loop. This can be much simpler

def unique_in_order(iterable):
  iterable = list(iterable)
  result = [iterable[0]]
  for i in range(1, (len(iterable))-1):
    if result[len(result)-1] != iterable[i]:
      result.append(iterable[i])
  return(result)

If you really want to do it without a result list, maybe you have some crazy memory constraints, use a while loop instead of a for loop. The parameters of the exit condition for a for loop is calculated one time at the start of the loop (in this case the length of the list), but the condition of a while loop is calculated every iteration.

Simon Notley · Accepted Answer · 2019-09-06 20:18:01Z

0

The problem is that you are iterating over the original length of the iterable. When you delete items form the list you shorten it. I can see you've tried to handle this by subtracting one from l_length but that has no effect as you've already initialised the iterable used for the for loop as range(0, l_lenth-1). Changing l_lenth will make no difference after this. You should use a while loop instead while i<l_lenth

answered Sep 6, 2019 at 20:18

Simon Notley

2,1363 gold badges14 silver badges21 bronze badges

Collectives™ on Stack Overflow

How to fix 'IndexError: list index out of range' using 'for in range:' while recursion

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related