Removing all duplicated pairs in a Python list

Question

I need a function to remove duplicated pairs from a list. The following is example list:

a = [1, 1, 1, 2, 3, 5, 4, 4, 5, 2, 3, 3, 2, 3, 1, 6, 6, 6, 6]

I need remove all pairs [a[i], a[i+1]] if a[i] == a[i+1] until all such pairs eliminated:

[1, 1, 1, 2, 3, 5, 4, 4, 5, 2, 3, 3, 2, 3, 1, 6, 6, 6, 6]

[1, 2, 3, 5, 5, 2, 2, 3, 1]

[1, 2, 3, 3, 1]

[1, 2, 1] - final list

I wrote a removepairs function:

def removepairs(list):
    result_prev = list
    while True:
        result = __removepairs_once__(result_prev)
        if len(result) == len(result_prev):
            return result
        else:
            result_prev = result

def __removepairs_once__(list):
    result = []
    most_recent_element = None
    for i in list:
        if i != most_recent_element:
            if most_recent_element:
                result.append(most_recent_element)
            most_recent_element = i
        else:
            most_recent_element = None
    if most_recent_element:
        result.append(most_recent_element)
    return result

Please help me to make it better.

Answer 1

I think you should try re-making __removepairs_once__ only using results. No most_recent_element.

So, you would want to retry you algorithm, most_recent_element can be results[-1]. Using this you should come to this stub code:

def _remove_pairs(list_):
    result = []
    for item in list:
        if item == results[-1]:
            # remove last item
            # don't add this item
        else:
            # add this item
    return result

Using this you should notice that it'll error if results is empty, this means you should use the else if it is. The if block is surprisingly simple, it's results.pop(). And the else is results.append(item).

def _remove_pairs(list_):
    results = []
    for item in list_:
        if results and item == results[-1]:
            results.pop()
        else:
            results.append(item)
    return results

A quick test of this actually (unsurprisingly) returns the final list that you wanted.

---

Don't use __{}__ for anything! Only use it for pythons magic functions!

You should also not use list but list_ as then you can still convert something to a list.

Answer 2

First of all, that is a really neat idea. I would change a couple things, though.

I don't think removepairs is a good name because it doesn't actually remove anything from the list; it returns a new list with the pairs removed. Therefore, I would call it get_singles.

You shouldn't use list as a variable name because it shadows the built-in type. If you decide later in your function that you want to convert a tuple to a list, you might use list(my_tuple). Oh no! 'list' object is not callable. I'm not using a list object; I am using list! Well, no actually. You can't have two things with the same name. You should always avoid using a name that shadows a built-in.

You don't need to check the length of result_prev for each iteration. Instead, keep a counter of the current position and check that against the length of result. (That will come in useful below). That is more efficient because you aren't re-calculating the length each time.

I wouldn't put __ around removepairs_once. When you do that, you are making the function private. That means that a wildcard import (from ... import *) will not include that function. I don't see that as a benefit. That function might be useful for other modules. I wouldn't bother renaming it, though, because I will present another solution that could just take it out.

My proposed solution creates just one list instead of a bunch of intermediate lists. It works by starting at index 0 and working up to the end. If a number is the same as a previous number, both numbers are removed and the index goes down so that we can re-check. Here it is:

def removepairs(numbers):
    i = 0 
    prev = None
    while i < len(numbers):
        number = numbers[i]
        if number == prev:
            numbers.pop(i) # Current
            numbers.pop(i - 1) # Previous
            i -= 1 # We deleted two, so the next is back one
        else:
            i += 1
        if i:
            prev = numbers[i - 1]
        else:
            prev = None

    return numbers

Answer 3

An alternative way could be to perform changes on the source list itself.

def remove_duplicate(l):
  curr_index = 0
  while curr_index < ( len(l) - 1 ):
    if l[curr_index] == l[curr_index + 1]:
      del l[curr_index:curr_index + 2]
      curr_index = 0
    else:
      curr_index += 1

source = [1, 1, 1, 2, 3, 5, 4, 4, 5, 2, 3, 3, 2, 3, 1, 6, 6, 6, 6]
remove_duplicate(source)