递归去除列表中的相邻重复元素

Question

我查了一下，找到了一个相似的例子，但在这个链接里找到的答案：从列表中移除相邻的重复元素，并不能运行这个问题的测试案例。所以到目前为止我只有这些：

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))

补充一下，虽然我明白上面链接的那个被接受的答案使用了itertools.groupby是可以工作的，但我觉得如果我从itertools导入groupby的话，就不能真正理解我的代码哪里出错了，这样也就失去了练习的意义。

Answer 1

问题出在你的返回语句上，

你返回的是

return remove_dups(thelist[i:])

输出总是列表中最后的n个单独元素。

就像上面提到的，

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]

这最终返回的是一个单独元素的列表，因为它没有考虑到第0个元素。

这里有一个递归的解决方案。

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

Answer 2

在使用递归处理列表的时候，大多数情况下我们需要返回一个子列表或者列表的一部分。这就需要我们检查一个终止条件，也就是列表是否为空。接下来我们有两种情况：

1. 当前的值和我们之前看到的最后一个值不同，所以我们想保留这个值。
2. 当前的值和我们之前看到的最后一个值相同，所以我们就把它丢掉，继续处理“剩下”的值。

这两种情况可以用下面的代码来表示：

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]

Answer 3

你的判断失败了，因为在

return thelist

你返回的是同一个列表，而不是评论中提到的副本。

试试这个：

return thelist[:]

Answer 4

from itertools import groupby

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

如果你真的想要一个递归的解决方案，我建议你可以试试这样的做法：

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 []