19

Google Python Class | List Exercise -

Given a list of numbers, return a list where all adjacent == elements have been reduced to a single element, so [1, 2, 2, 3] returns [1, 2, 3]. You may create a new list or modify the passed in list.

My solution using a new list is -

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

The question even suggests that it could be done by modifying the passed in list. However, the python documentation warned against modifying elements while iterating a list using the for loop.

I am wondering what else can I try apart from iterating over the list, to get this done. I am not looking for the solution, but maybe a hint that can take me into a right direction.

UPDATE

-updated the above code with suggested improvements.

-tried the following with a while loop using suggested hints -

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
2

17 Answers 17

20

Here's the traditional way, deleting adjacent duplicates in situ, while traversing the list backwards:

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

Update: If you want a generator but (don't have itertools.groupby or (you can type faster than you can read its docs and understand its default behaviour)), here's a six-liner that does the job:

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

Update 2: Concerning the baroque itertools.groupby() and the minimalist object() ...

To get the dedupe_adjacent effect out of itertools.groupby(), you need to wrap a list comprehension around it to throw away the unwanted groupers:

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

... or muck about with itertools.imap and/or operators.itemgetter, as seen in another answer.

Expected behaviour with object instances is that none of them compares equal to any other instance of any class, including object itself. Consequently they are extremely useful as sentinels.

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

It's worth noting that the Python reference code for itertools.groupby uses object() as a sentinel:

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

and that code does the right thing when you run it:

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

Update 3: Remarks on forward-index in-situ operation

The OP's revised code:

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

is better written as:

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
6
  • Python 1.5.2. Do you run it on FreeDOS? Aug 11, 2010 at 23:32
  • @aaronasterling: No, on Windows XP, and only very occasionally, like when I see someone using itertools.groupby etc to do something simple ;-) Aug 11, 2010 at 23:52
  • @John Machin. I like your algorithm a lot. +1 in a minute when my votes reup. Aug 11, 2010 at 23:59
  • It's a bit hacky to do prev = object( ) and hope that object( ) isn't the first item in the iterable! It would be more correct, though slightly less elegant, to do iterable = iter( iterable ) (to ensure that it is an iterator) and then prev = next( iterable ).
    – Katriel
    Aug 12, 2010 at 9:01
  • 1
    @katrielalex: All I'm hoping is that object() instances continue to be "featureless" ;-) Check out the results of object() == object() and dir(object()) in any Python version from 2.2 onwards. Aug 12, 2010 at 10:44
12

Use a generator to iterate over the elements of the list, and yield a new one only when it has changed.

itertools.groupby does exactly this.

You can modify the passed-in list if you iterate over a copy:

for elt in theList[ : ]:
    ...
5
  • when iterating over a copy, am I not modifying the copy and not the actual passed-in list? Aug 12, 2010 at 8:31
  • Yes. You have to refer explicitly to the original list, using e.g. the index of the element.
    – Katriel
    Aug 12, 2010 at 9:00
  • I disagree with this. If you remove elements from the original list even when iterating over a copy you can make a number of mistakes. I think the best way to modify elements in a list one is iterating over is to iterate over the list backwards and modify the elements by index.
    – Paul Seeb
    Feb 28, 2012 at 21:55
  • The answer: list(x.next() for i, x in groupby(my_list))
    – est
    Dec 8, 2017 at 8:06
  • list(i for i, x in groupby(my_list))
    – anonymous
    May 31, 2018 at 6:11
8

Just to show one more way here is another single liner version without indexes:

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

The not part puts the last value to result as only a ends up to result.

6

As usual, I am just here to advertise the impressive recipes in the Python itertools documentation.

What you are looking for is the function unique_justseen:

from itertools import imap, groupby
from operator import itemgetter

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

list(unique_justseen([1,2,2,3])) # [1, 2, 3]
3

Well, katrielalex is right about itertools, but the OP seems to be rather more interested (or should be!) in learning to manipulate the basics of the built-in data structures. As for manipulating a list in place, it does need thought, but my recommendation would be to read through this section of the documentation and try a few list methods (hint: list.pop(), list.remove(), and learn everything about slices.)

The posted code could be simplified, by the way (you should however add handling of error conditions):

def remove_adjacent(nums):
  a = nums[:1]
  for item in nums[1:]:
    if item != a[-1]:
      a.append(item)
  return a
2
  • interesting to find, nums[0] returns an int, while nums[:1] returns a list with a single element! thank you! Aug 11, 2010 at 16:26
  • and through the magic of slicing, nums[:1] will return an empty list if nums is empty, giving you correct behavior in case an empty list is provided as input. By contrast nums[0] would raise a KeyError if nums comes in as an empty list.
    – PaulMcG
    Aug 11, 2010 at 19:04
2

Extremely elegant solution from Google (source is here: https://developers.google.com/edu/python/exercises/basic):

def remove_adjacent(nums):
    result = []
    for num in nums:
        if len(result) == 0 or num != result[-1]:
            result.append(num)
    return result
1

You can use list comprehension. For example something like this should do the job:

def remove_adjacent(L):
  return [elem for i, elem in enumerate(L) if i == 0 or L[i-1] != elem]

or:

def remove_adjacent(L):
  return [L[i] for i in xrange(len(L)) if i == 0 or L[i-1] != L[i]]
1

Try this:

def remove_adjacent(nums):
  result = []
  if len(nums) > 0:
    result = [nums[0]]
    for i in range(len(nums)-1):
        if nums[i] != nums[i+1]:
            result.append(nums[i+1])

  return result
1

itertools.groupby is superior, but there is also

reduce(lambda x, y: x + [y] if x[-1] != y else x, seq[1:], seq[0:1])

e.g.

>>> seq = [[1,1], [2,2], [3,3], [3,3], [2,2], [2,2], [1,1]]
>>> print reduce(lambda x, y: x + [y] if x[-1] != y else x, seq[1:], seq[0:1])
[[1, 1], [2, 2], [3, 3], [2, 2], [1, 1]]

When coming from functional languages where this sort of thing is done with a fold, then using reduce often feels natural.

0

You can modify a list you're iterating over if you use indices explicitly:

def remove_adjacent(l):
  if len(l)<2:
    return l
  prev,i = l[0],1
  while i < len(l):
    if l[i] == prev:
      del l[i]
    else:
      prev = l[i]
      i += 1

It doesn't work with iterators because iterators don't "know" how to modify the index when you remove arbitrary elements, so it's easier to just forbid it. Some languages have iterators with functions to remove the "current item".

2
  • (1) Don't use "l" as a variable name; in some fonts it looks too close to "1" (2) Your function returns the original list if its length is less than 2, otherwise it returns None ... somewhat inconsistent. Aug 12, 2010 at 7:53
  • l is a perfectly good variable name. If your code font doesn't distinguish between l, I, 1, 0, O, then you need a better font.
    – tc.
    Aug 12, 2010 at 16:33
0

@katrielalex's solution is more pythonic, but if you did need to modify the list in-place without making a copy, you could use a while loop and break when you catch an IndexError. e.g.

nums = [1,1,1,2,2,3,3,3,5,5,1,1,1]
def remove_adjacent(nums):
    """Removes adjacent items by modifying "nums" in-place. Returns None!"""
    i = 0
    while True:
        try:
            if nums[i] == nums[i+1]:
                # Letting you figure this part out, 
                # as it's a homework question
        except IndexError:
            break
print nums
remove_adjacent(nums)
print nums

Edit: pastebin of one way to do it here, in case you get stuck and want to know..

1
  • I tried out the hint and have updated with my attempt. Aug 11, 2010 at 16:46
0

def remove_adjacent(nums):

newList=[]

for num in nums:

    if num not in newList:

        newList.append(num)

newList.sort()

return  newList
1
  • This does not answer the question.
    – AndJM
    Dec 15, 2015 at 15:02
0

Another approach. Comments welcome.

def remove_adjacent(nums):
    '''modifies the list passed in'''
    l, r = 0, 1
    while r < len(nums):
        if nums[l] == nums[r]:
            r += 1
        else:
            l += 1
            nums[l] = nums[r]
            r += 1
    del nums[l+1:]
0

Seeing the code written by Google is a humbling lol. This is what I came up with:

def remove_adjacent(nums):
   rmvelement = []
   checkedIndex = []
   for num in nums:
      if nums.index(num) not in checkedIndex:
         index = nums.index(num)
         checkedIndex.append(index)
         skip = False
      else:
         skip = True

   if skip == False:
      for x in nums[index+1:]:
         if x == num:
            rmvelement.append(x)
         else:
            break

   [nums.remove(_) for _ in rmvelement]
   return nums
0

This should work for a transparent (albeit roundabout) solution:

def remove_adjacent(nums):

    numstail = [i for i in range(0,len(nums))] 
    nums = nums + numstail

    for i in nums:
        if nums[i] == nums[i-1]:
            del nums[i]

    return nums[:-len(numstail)]

The logic is as follows:

  • Create a tail-list equal to the length of the original list of numbers and append this to the end of the original list.
  • Run a 'for-loop' that checks if a given element of nums is the same as the previous element. If so, delete it.
  • Return the new nums list, with the necessary deletions, up to len(numtails) index positions from the end of the list.

(numstail is defined to avoid indices being out of range for any length list)

0
def removeDupAdj2(a):
    b=[]
    for i in reversed(range(1,len(a))):
        if(a[i-1] == a[i]):
            del(a[i])
            #print(a)
    return a

a = [int(i) for i in '1 2 3 3 4 4 3 5 4 4 6 6 6 7 8 8 8 9 1 1 0 0'.split(' ')]
a

res = removeDupAdj2(a)
res
-3

Since you are in a Python class, I'm going to guess that you are new to the language. Thus, for you and any other beginners out there, I wrote a simple version of the code to help others get through the logic.

original= [1, 2, 2, 3]
newlist=[]

for item in original:
    if item in newlist:
        print "You don't need to add "+str(item)+" again."
    else:
        newlist.append(item)
        print "Added "+str(item)

print newlist
1
  • 1
    but it asks to remove only adjacent items, the above code will not let any duplicates in irrespective of their position, so inehrently [1,2,3,2] will produce [1,2,3] whereby it should produce [1,2,3,2] Aug 11, 2010 at 16:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.