从列表中移除相邻的重复元素

Question

谷歌的Python课程 | 列表练习 -

给定一个数字列表，返回一个新列表，其中所有相邻的相同元素都被合并成一个元素，比如说 [1, 2, 2, 3] 会返回 [1, 2, 3]。你可以创建一个新列表，也可以直接修改传入的列表。

我用新列表的方式解决这个问题是 -

def remove_adjacent(nums):
  a = []
  for item in nums:
    if len(a):
      if a[-1] != item:
        a.append(item)
    else: a.append(item)        
  return a

这个问题甚至提到可以通过修改传入的列表来完成。不过，Python的文档警告说在用for循环遍历列表时，不要修改元素。

我在想，除了遍历列表，还有什么其他方法可以做到这一点。我并不是在寻找答案，只是希望能得到一些提示，帮助我朝正确的方向前进。

更新

- 我已经根据建议对上面的代码进行了更新。

- 尝试了以下用while循环的方法，使用了建议的提示 -

def remove_adjacent(nums):
  i = 1
  while i < len(nums):    
    if nums[i] == nums[i-1]:
      nums.pop(i)
      i -= 1  
    i += 1
  return nums

Answer 1

这里再给大家展示一种方法，这是一行代码的写法，不需要用到索引：

def remove_adjacent(nums):
     return [a for a,b in zip(nums, nums[1:]+[not nums[-1]]) if a != b]

这里的“not”部分会把最后一个值放到结果中，因为只有“a”会被放到结果里。

Answer 2

这里介绍一种传统的方法，边遍历列表边删除相邻的重复项，不过是从后往前进行的：

Python 1.5.2 (#0, Apr 13 1999, 10:51:12) [MSC 32 bit (Intel)] on win32
Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>> def dedupe_adjacent(alist):
...     for i in xrange(len(alist) - 1, 0, -1):
...         if alist[i] == alist[i-1]:
...             del alist[i]
...
>>> data = [1,2,2,3,2,2,4]; dedupe_adjacent(data); print data
[1, 2, 3, 2, 4]
>>> data = []; dedupe_adjacent(data); print data
[]
>>> data = [2]; dedupe_adjacent(data); print data
[2]
>>> data = [2,2]; dedupe_adjacent(data); print data
[2]
>>> data = [2,3]; dedupe_adjacent(data); print data
[2, 3]
>>> data = [2,2,2,2,2]; dedupe_adjacent(data); print data
[2]
>>>

更新：如果你想要一个生成器，但又没有 itertools.groupby，或者你打字的速度比阅读它的文档和理解默认行为的速度快，这里有一个六行代码可以完成这个任务：

Python 2.3.5 (#62, Feb  8 2005, 16:23:02) [MSC v.1200 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> def dedupe_adjacent(iterable):
...     prev = object()
...     for item in iterable:
...         if item != prev:
...             prev = item
...             yield item
...
>>> data = [1,2,2,3,2,2,4]; print list(dedupe_adjacent(data))
[1, 2, 3, 2, 4]
>>>

更新 2：关于复杂的 itertools.groupby() 和简单的 object() ...

要从 itertools.groupby() 中获得去重相邻的效果，你需要在它周围包裹一个列表推导式，以丢弃不需要的分组：

>>> [k for k, g in itertools.groupby([1,2,2,3,2,2,4])]
[1, 2, 3, 2, 4]
>>>

...或者可以使用 itertools.imap 和/或 operators.itemgetter，就像另一个答案中提到的那样。

使用 object 实例时，值得注意的是，它们之间没有任何一个实例会和其他任何类的实例相等，包括 object 自身。因此，它们作为哨兵非常有用。

>>> object() == object()
False

值得一提的是，Python 的参考代码 中，itertools.groupby 使用 object() 作为哨兵：

self.tgtkey = self.currkey = self.currvalue = object()

而且当你运行这段代码时，它会正确地执行：

>>> data = [object(), object()]
>>> data
[<object object at 0x00BBF098>, <object object at 0x00BBF050>]
>>> [k for k, g in groupby(data)]
[<object object at 0x00BBF098>, <object object at 0x00BBF050>]

更新 3：关于前向索引原地操作的说明

原作者修改后的代码：

def remove_adjacent(nums):
  i = 1
  while i < len(nums):    
    if nums[i] == nums[i-1]:
      nums.pop(i)
      i -= 1  
    i += 1
  return nums

可以更好地写成：

def remove_adjacent(seq): # works on any sequence, not just on numbers
  i = 1
  n = len(seq)
  while i < n: # avoid calling len(seq) each time around
    if seq[i] == seq[i-1]:
      del seq[i]
      # value returned by seq.pop(i) is ignored; slower than del seq[i]
      n -= 1
    else:
      i += 1
  #### return seq #### don't do this
  # function acts in situ; should follow convention and return None

Answer 3

使用生成器来遍历列表中的元素，只有当元素发生变化时才返回一个新的元素。

itertools.groupby 就是用来做这个的。

如果你遍历一个列表的副本，你可以修改原来的列表：

for elt in theList[ : ]:
    ...