2

I have to write a function that takes a list and char gets a list with all instances of the char removed.

I'm just not quite getting anywhere with the sublists. I've been programming in Java for some time but I'm new to python.

My code:

def my_remove(the_char, the_list):

    if the_list == []:#works
        return the_list

    if isinstance(the_list[0],list): #if the first element in the list is, itself, a list
        #remove the character from the first element/list and move on to other list elements in the main list
    else:
        print 'else'
        return the_list

    print 'regular return'
    return the_list
8
  • 1
    Do you know how to program recursive functions in Java? The structure is largely the same in Python as far as I know.
    – glibdud
    Sep 9, 2019 at 17:23
  • Do you have to write a recursive function?
    – martineau
    Sep 9, 2019 at 17:47
  • 6
    Please don't fundamentally change the question after you have received answers. I have rolled back your edit. Sep 11, 2019 at 6:59
  • 4
    Please don't make more work for others by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license, for SE to distribute the content (i.e. regardless of your future choices). By SE policy, the non-vandalized version is distributed. Thus, any vandalism will be reverted. Please see: How does deleting work? …. If permitted to delete, there's a "delete" button below the post, on the left, but it's only in browsers, not the mobile app.
    – Makyen
    Sep 11, 2019 at 7:00
  • 4
    If you have a different question (in a different language...) simply ask a new question. By changing completely a question you disrespect the people who took the bother and time to answer the original one. Look how much @user633183 put into his answer. If you change the question completely, all his work was for nothing...
    – Tomerikoo
    Sep 11, 2019 at 7:01

2 Answers 2

2

The key to this recursive problem (and most) is understanding mathematical induction -

def my_remove(the_char, the_list):
  if the_list == []: #1
    return the_list

  elif isinstance(the_list[0],list): #2
    return my_remove(the_char, the_list[0]) \
         + my_remove(the_char, the_list[1:])

  elif the_list[0] == the_char: #3
    return my_remove(the_char, the_list[1:])

  else: #4
    return [ the_list[0] ] + my_remove(the_char, the_list[1:])

input = ['a','z',['z','b',['c','z','z']],[['d']],'z'] 

print(my_remove('z', input))
# ['a','b','c','d']

In the numbered comments -

  1. terminating condition and base case: when the input is empty, return an empty output

  2. otherwise, by induction, the list is not empty. If the first element of the list is another list, combine the result of calling my_remove on the first element and my_remove on the tail of the list, list[1:]

  3. otherwise, by induction, the list is not empty and the first element of the list is not a list. If the first element matches the char, simply call my_remove on the tail of the list.

  4. otherwise, by induction, the list is not empty and the first element is of the list is not a list, and the first element of the list does not match the char. Include the first element of the list in the output and combine it with my_remove called on the tail of the list


Your question explicitly says that helper functions cannot be used. This is most likely an indication of a bad programming teacher. Helper functions make it possible to remove complexity from your program, thereby gaining a complexity-free mind.

Given some generic functions for working on lists -

def isEmpty(l):
  return len(l) == 0

def isList(l):
  return isinstance(l, list)

def head(l):
  return l[0]

def tail(l):
  return l[1:]

We can write my_remove with a richer semantics that immediately communicates its intentions to the reader -

def my_remove(x, lst):
  if isEmpty(lst):
    return lst

  elif isList(head(lst)):
    return my_remove(x, head(lst)) \
         + my_remove(x, tail(lst))

  elif head(lst) == x:
    return my_remove(x, tail(lst))

  else:
    return [ head(lst) ] + my_remove(x, tail(lst))

The output is the same, of course -

print(my_remove('z', input))
# ['a','b','c','d']

These helpers could be further improved to protect the programmer for their misuse. Ie, raising a RuntimeWarning is a good way to let you know you made a mistake with your inductive reasoning -

def isEmpty(l):
  return isList(l) and len(l) == 0

def isList(l):
  return isinstance(l, list)

def head(l):
  if isEmpty(l):
    raise RuntimeWarning('head called on empty list')
  else:
    return l[0]

def tail(l):
  if isEmpty(l):
    raise RuntimeWarning('tail called on empty list')
  else:
    return l[1:]
2
  • This works except for the fact that it flattens the list. How would you go about keeping the list full of sublists?
    – User1789
    Sep 10, 2019 at 22:57
  • in elif isList(head(lst)): ... change the my_remove(...) + my_remove(...) case to [ my_remove(...) ] + my_remove(...)
    – Mulan
    Sep 10, 2019 at 23:21
0

There are two cases to handle:

  1. when word is list

  2. when word is str

For case 1, when word is an empty list (base case) return an empty list. Return the concatenated list of a list of the function invoked with the first item in the list and the result of the function invoked with the remaining items in the list.

For case 2, when the word is an empty string (base case) return an empty string, when the first character of the word matched the character searched for, return the result of calling the recursive function with the rest of the string. Otherwise, concatenate the first character together with the result of calling the recursive function with the rest of the string.

import doctest

def remove(word, char):
  """
  >>> remove([['swan'], ['elephant'], 'snake'], 'e')
  [['swan'], ['lphant'], 'snak']
  >>> remove(['swan', [['elephant']], ['snake']], 'e')
  ['swan', [['lphant']], ['snak']]
  """
  if isinstance(word, list):
    if word == []:
      return []
    head, tail = word[0], word[1:]
    return [remove(head, char)] + remove(tail, char)

  if isinstance(word, str):
    if word == '':
      return ''
    head, tail = word[0], word[1:]
    if head == char:
        return remove(tail, char)
    return head + remove(tail, char)

doctest.testmod()
1
  • NB this function can return None if any element (word) is neither a list nor a str
    – Mulan
    Sep 9, 2019 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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