Recursive list slicing in Python

Question

I am working on splicing unwanted sections in a given list, and I'd like to do it recursively. I'm struggling to figure out the right way to delete something based off a set of tokens. For example, if I have ['a','b','c','d','e'], I'm trying to recursively remove from 'b' to 'd', which would result in ['a','e'].

Here is what has gotten me the closest thus far.

lines = """
variable "ops_manager_private" {
  default     = false
  description = ""
}

variable "optional_ops_manager" {
  default = false
}

/******
* RDS *
*******/

variable "rds_db_username" {
  default = ""
}

variable "rds_instance_class" {
  default = ""
}

variable "rds_instance_count" {
  type    = "string"
  default = 0
}
"""

def _remove_set(target: list, start: str, stop: str, delete=False):
    if not target:
        return []
    elif target[0] == start:
        return target[0] + _remove_set(target[1:], start, stop, delete=True)
    elif delete is True:
        return _remove_set(target[1:], start, stop, delete=True)
    elif target[0] == stop:
        return target[0] + _remove_set(target[1:], start, stop, delete=False)
    else:
        return target[0] + _remove_set(target[1:], start, stop, delete=False)


if __name__ == __main__:
    results = _remove_set(lines.splitlines(), 'ops_', '}\n')

Then I get this error:

Traceback (most recent call last):
# large recursive traceback
TypeError: can only concatenate str (not "list") to str

What is the right way to recursively slice a list?

This doesn't seem like a particularly good case for recursion. Is there any reason you want to use recursion here? — Blorgbeard
– Blorgbeard, Commented May 8, 2019 at 23:45
Perhaps iterate over the list, matching beginning and end tokens, and simply don't add items that are within those sections? — jspcal
– jspcal, Commented May 8, 2019 at 23:45
But try replacing target[0] with [target[0]] to fix your error. — Blorgbeard
– Blorgbeard, Commented May 8, 2019 at 23:47
Try returning an empy string in your base case instead of an empy list. — wwii
– wwii, Commented May 8, 2019 at 23:52
When asking questions about code that produces an Exception, please include the complete Traceback. — wwii
– wwii, Commented May 8, 2019 at 23:54

jspcal · Accepted Answer · 2019-05-08 23:56:19Z

1

You can skip elements between the start token 'b' and end token 'd' with a loop:

items=['a','b','c','d','e']
result=[]
skip=False

for item in items:
    if item == 'b':
        skip = True
    elif not skip:
        result.append(item)
    elif item == 'd':
        skip = False

print(result)
# ['a', 'e']

answered May 8, 2019 at 23:56

jspcal

52k7 gold badges76 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mark · Accepted Answer · 2019-05-09 00:04:06Z

1

Typically a recursive approach would look at one element and pass the rest back to the function. If you do this you only need to decide whether to include the one element + the result of the recursion. Something like:

def remove(arr, delete):
    ''' remove element from arr in in delete list'''
    if not arr:    # edge condition
        return arr
    n, *rest = arr 

    if n in delete:
        return remove(rest, delete)
    else:
        return [n] + remove(rest, delete)

l = ['a','b','c','d','e']

remove(l, ['d', 'b'])

answered May 9, 2019 at 0:04

Mark

92.7k8 gold badges116 silver badges156 bronze badges

Comments

a_guest · Accepted Answer · 2019-05-09 00:09:45Z

0

You can use a generator with itertools.takehwile to yield the elements that are not between the start/stop markers:

import itertools as it

def remove(items, start, stop):
    items = iter(items)
    while True:
        yield from it.takewhile(start.__ne__, items)
        if all(x != stop for x in items):
            break

print(list(remove('abcde', 'b', 'd')))  # ['a', 'e']
print(list(remove('abcdefbghdi', 'b', 'd')))  # ['a', 'e', 'f', 'i']

answered May 9, 2019 at 0:09

a_guest

36.7k15 gold badges75 silver badges137 bronze badges

Comments

a_guest · Accepted Answer · 2019-05-09 10:25:43Z

0

For a recursive solution you can use the (list|str|tuple).index methods instead of iterating over the elements one by one:

def remove(items, start, stop):
    try:
        i = items.index(start)
        j = items.index(stop, i)
    except ValueError:
        return items[:]
    return items[:i] + remove(items[j+1:], start, stop)

print(remove('abcde', 'b', 'd'))  # 'ae'
print(remove('abcdefbghdi', 'b', 'd'))  # 'aefi'

Note that this only deletes items from explicitly closed sections, i.e. no implicit closing at the end:

print(remove('abc', 'b', 'd'))  # 'abc'

answered May 9, 2019 at 10:25

a_guest

36.7k15 gold badges75 silver badges137 bronze badges

Collectives™ on Stack Overflow

Recursive list slicing in Python

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related