递归删除列表中的相邻副本

我抬起头，发现一个很接近的例子，但在这个链接中找到的答案：Remove adjacent duplicate elements from a list将不会运行这个问题的测试用例。所以这是我到目前为止有：递归删除列表中的相邻副本

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中导入了grouby，就会击败练习的目的。

来源

2014-03-26 Dave Lee

它必须是递归的吗？你能排序它，然后迭代它吗？ – AndyG

我会认为排序是错误的，否则你只是做排序（设置（列表）） –

@andyG是的，它必须是递归的 –

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

来源

2014-03-26 20:11:15

你的断言失败，因为在

return thelist

在评论中指定要返回相同的列表，而不是一个副本。

尝试：

return thelist[:]

来源

2014-03-26 20:05:15 Hyperboreus

你是对的，但那不会不会改变我最终的结果 - 我想我需要改变第一组代码的最后三行。 –

当使用递归处理列表是大部分时间的问题返回一个子列表或该列表的一部分。这使终止案例测试一个空的列表。然后你有两种情况：

电流值是从我们看到的，所以我们要保持它的
当前值是一样的，最后一个我们看到，所以我们放弃它的最后一个不同并继续迭代值的“休息”。在此代码

哪个翻译：

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]

来源

2014-03-26 20:27:39 bvidal

谢谢你的深入解释 - 我很欣赏线条间的意见。 –

问题是在你return语句，

要返回

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]

它最终返回单个元素的列表，因为它不考虑Oth元素。

这里是递归解决方案。

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

来源

2014-03-26 20:34:56 Roshan

你是对的！我一直只获得一个价值。谢谢。 –

我已编辑解决方案的答案，您可以查看它。我认为它更好的解决方案。 – Roshan

递归删除列表中的相邻副本

回答

相关问题