CODEWITHSUNDEEP
pythonrecursion
Dave Lee
Dave Lee

Reputation: 9

recursively remove adjacent duplicates in a list

I looked up and found a close example, but the answer found in this link: Remove adjacent duplicate elements from a list won't run the test cases for this problem. So this is all I have so far:

def remove_dups(thelist):
    """Returns: a COPY of thelist with adjacent duplicates removed.

    Example: for thelist = [1,2,2,3,3,3,4,5,1,1,1],
    the answer is [1,2,3,4,5,1]

    Precondition: thelist is a list of ints"""
    i = 1
    if len(thelist) == 0:
        return []
    elif len(thelist) == 1:
        return thelist
    elif thelist[i] == thelist[i-1]:
        del thelist[i]
    return remove_dups(thelist[i:])


def test_remove_dups():
    assert_equals([], remove_dups([]))
    assert_equals([3], remove_dups([3,3]))
    assert_equals([4], remove_dups([4]))
    assert_equals([5], remove_dups([5, 5]))
    assert_equals([1,2,3,4,5,1], remove_dups([1,2,2,3,3,3,4,5,1,1,1]))

# test for whether the code is really returning a copy of the original list
    mylist = [3]
    assert_equals(False, mylist is remove_dups(mylist))

EDIT while I do understand that the accepted answer linked above using itertools.groupby would work, I think it wouldn't teach me what's wrong with my code & and would defeat the purpose of the exercise if I imported grouby from itertools.

Upvotes: 1

Views: 4925

Answers (4)

Roshan
Roshan

Reputation: 1459

problem is with your return statement,

you are returning 

return remove_dups(thelist[i:])

output will be always last n single element of list

like for above soon,

print remove_dups([1,2,2,3,3,3,4,5,1,1,1])
>>> [1] #as your desired is [1,2,3,4,5,1]

which returns finally a list of single element as it don't consider Oth element.

here is recursive solution.

def remove_dups(lst):
    if len(lst)>1:

        if lst[0] != lst[1]:
            return [lst[0]] + remove_dups(lst[1:])

        del lst[1]
        return remove_dups(lst)
    else:
        return lst

Upvotes: 0

El Bert
El Bert

Reputation: 3026

When using recursion with list it is most of the time a problem of returning a sub-list or part of that list. Which makes the termination case testing for an empty list. And then you have the two cases:

  1. The current value is different from the last one we saw so we want to keep it
  2. The current value is the same as the last one we saw so we discard it and keep iterating on the "rest" of the values.

Which translate in this code: 

l = [1,2,2,3,3,3,4,5,1,1,1]

def dedup(values, uniq):
  # The list of values is empty our work here is done
  if not values:
    return uniq
  # We add a value in 'uniq' for two reasons:
  #  1/ it is empty and we need to start somewhere
  #  2/ it is different from the last value that was added
  if not uniq or values[0] != uniq[-1]:
    uniq.append(values.pop(0))
    return dedup(values, uniq)
  # We just added the exact same value so we remove it from 'values' and 
  # move to the next iteration
  return dedup(values[1:], uniq)

print dedup(l, []) # output: [1, 2, 3, 4, 5, 1]

Upvotes: 0

Hugh Bothwell
Hugh Bothwell

Reputation: 56654

from itertools import groupby

def remove_dups(lst):
    return [k for k,items in groupby(lst)]

If you really want a recursive solution, I would suggest something like

def remove_dups(lst):
    if lst:
        firstval = lst[0]

        # find lowest index of val != firstval
        for index, value in enumerate(lst):
            if value != firstval:
                return [firstval] + remove_dups(lst[index:])

        # no such value found
        return [firstval]
    else:
        # empty list
        return []

Upvotes: 1

Hyperboreus
Hyperboreus

Reputation: 32429

Your assertion fails, because in

return thelist

you are returning the same list, and not a copy as specified in the comments.

Try:

return thelist[:]

Upvotes: 0

Related Questions