logo标签列表

递归地清空嵌套列表并保留其结构

pythonalgorithmlistrecursion
4

我正在尝试编写一个函数，它可以读取一个包含列表的列表，并返回相同的列表结构但没有元素。

def remove_from_list(l):
    for e in l:
        if isinstance(e, list):
            remove_from_list(e)
        else:
            l.remove(e)
    return l

因此，对于这样的输入：

[1, 2, [], [3,[4]], 5]

我应该得到像这样的东西：
[[], [[]]]

我尝试使用以下输入：

[1, 2, [], [3,[4]], 5]
[1, 2, [], [2,[3]], 2]

并获取了以下输出结果：

[2, [], [[4]]]
[[], [[3]], 2]

这非常令人困惑，因为两个列表的结构是相同的，只有元素不同。所以我不仅得到了一个错误，而且得到了另一个错误。帮助解决函数并解释我的错误将非常感激。

确实，这是初学者的错误。您不应该在迭代期间删除列表元素。 - cs95
1
你是否一定要直接修改传入的列表？ - juanpa.arrivillaga
1
@cᴏʟᴅsᴘᴇᴇᴅ 不是这样的。可以使用反向迭代和del，不需要复制。 - wim
@wim，你提到了一个有趣的挑战，涉及到递归列表。你认为我在回答中尝试解决它的方式如何？ - גלעד ברקן
@גלעדברקן 很好！+1 - wim
1
可能是递归删除列表元素 Python的重复内容。 - BDL
5个回答
6
关键问题在于 for 循环具有固定的迭代次数，但是当你在循环内删除列表时，你正在缩小它们。因此，循环指针保持不变，而列表变得更小。最终，循环无法完成迭代。 选项1
作为一个简单的解决方法，你可以在函数内部创建一个新列表。这应该更简单，并且不会改变你的原始列表。
def remove_from_list(l):
    r = []
    for e in l:
        if isinstance(e, list):
            r.append(remove_from_list(e))
    return r


>>> remove_from_list([1, 2, [], [3,[4]], 5])
[[], [[]]]

此外，由于您只附加空结构，因此这比创建数据副本和后续的删除调用更快。

选项2
在wim的想法的基础上进行反向迭代，并使用del如果您想要原地修改列表。

def remove_from_list(l):
    r = []
    for i in range(len(l) - 1, -1, -1):
        if isinstance(l[i], list):
            remove_from_list(l[i])
        else:
            del l[i]


>>> l = [1, 2, [], [3,[4]], 5]
>>> remove_from_list(l)
>>> l
[[], [[]]]

我建议从良好的实践角度出发，要么返回一个副本，要么就直接修改而不返回，但不能两者都做。
您可以使用timeit比较来确定哪种方法在您的数据上运行得更快。
首先，是设置 -
def remove_from_list(l):
    r = []
    for e in l:
        if isinstance(e, list):
            r.append(remove_from_list(e))
    return r

def remove_from_list_reverse_del(l):
    r = []
    for i in range(len(l) - 1, -1, -1):
        if isinstance(l[i], list):
            remove_from_list(l[i])
        else:
            del l[i]


def remove_from_list_copy(l):
    for e in l[:]: # make a copy by slicing
        if isinstance(e, list):
            remove_from_list_copy(e)
        else:
            l.remove(e)
    return l

y = [1, 2, [], [3,[4]], 5]
z = copy.deepcopy(y  * 10000)

接下来是时间安排 - 

%timeit remove_from_list(z)
19.3 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


%%timeit
z2 = copy.deepcopy(z)    # copying because this function mutates the original
remove_from_list_reverse_del(z2)

78.6 ms ± 157 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

虽然在创建z2时浪费了很多时间。

1
嗨，当列表包含对自身的引用时，会导致崩溃。 - wim
1
好的，他们都会。 - cs95
2
是的，我从未说过其他答案更好。你问它在技术上是否有缺陷。 - wim
@wim 好的，我已经添加了反向删除，但是处理递归列表超出了我愿意为这样一个问题付出的关注范围。 - cs95
4
什么时候才能再次使用好的递归呢？（顺便说一句，这个答案也处理包含对自身引用的列表。）
def f(l, i, ids):
  if i >= len(l):
    return l
  if isinstance(l[i], list):
    if not id(l[i]) in ids:
      ids.add(id(l[i]))
      f(l[i], 0, ids)
    return f(l, i + 1, ids)
  else:
    del l[i]
    return f(l, i, ids)

a = [1, 2, [], [3,[4]], 5]
a.append(a)
a[3].append(a[3])

print a # [1, 2, [], [3, [4], [...]], 5, [...]]
print f(a, 0, set([id(a)])) # [[], [[], [...]], [...]]

（关于你的误解 - 正如coldspeed所提到的，如果在for循环期间删除列表的某些部分，则可能会导致意外结果，因为迭代的范围在开始之前设置，但列表在中途被修改。）
什么也没发生。这里的所有答案都是递归的？ - cs95
递归，是的；老式，不是。 - גלעד ברקן
3
这是另一种使用递归的方法：
def remove_from_list (l):
  if not l:
    return []
  elif isinstance (l[0], list):
    return [remove_from_list (l[0])] + remove_from_list (l[1:])
  else:
    return remove_from_list (l[1:])

print (remove_from_list ([1, 2, [], [3, [4]], 5]))
# [[], [[]]]

如果您喜欢用这种方式思考问题，那么一些通用函数就能让事情变得更好。
def is_empty (l):
  return not l

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

def head (l):
  return l[0]

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

def remove_from_list (l):
  if is_empty (l):
    return []
  elif is_list (head (l)):
    return [remove_from_list (head (l))] + remove_from_list (tail (l))
  else:
    return remove_from_list (tail (l))

print (remove_from_list ([1, 2, [], [3, [4]], 5]))
# [[], [[]]]

它不会改变输入内容。
data = [1, 2, [], [3, [4]], 5]

print (remove_from_list (data))
# [[], [[]]]

print (data)
# [1, 2, [], [3, [4]], 5]

以下是一种尾递归版本，可以做到不会导致栈溢出，详见此处 (变化部分为加粗)

<b>def identity (x):
  return x</b>

def remove_from_list (l<b>, k = identity</b>):
  if is_empty (l):
    return <b>k (</b>[]<b>)</b>
  elif is_list (head (l)):
    return remove_from_list (head (l)<b>, lambda x:</b>
      remove_from_list (tail (l)<b>, lambda y:</b>
        <b>k (</b>[<b>x</b>] + <b>y)</b>))
  else:
    return remove_from_list (tail (l)<b>, k)</b>

print (remove_from_list (data))
# [[], [[]]]
3

简单递归

def remove_from_list(l):
  if l == []:
    return []
  elif not isinstance(l[0], list):
    return remove_from_list(l[1:])
  else:
    return [remove_from_list(l[0])] + remove_from_list(l[1:])

有点更加复杂
def remove_from_list(l):
  def remove_inner(l_in,l_out):
    if l_in == []:
      return l_out
    elif not isinstance(l_in[0], list) or l[0] == []:
      return remove_inner(l_in[1:],l_out)
    else:
      return remove_inner(l_in[1:], l_out + [remove_from_list(l_in[0])])
  return remove_inner(l,[])

print(remove_from_list([1, 2, [], [3,[4]], 5]))
2
问题在于您正在遍历同一个列表时从中删除元素。一种解决方法是先复制一份列表，然后对副本进行遍历操作，例如：
def remove_from_list(l):
    for e in l[:]: # make a copy by slicing
        if isinstance(e, list):
            remove_from_list(e)
        else:
            l.remove(e)
    return l

结果：

>>> remove_from_list([1, 2, [], [3,[4]], 5])
[[], [[]]]
这种行为的解释来自于Python文档：

当循环修改序列时（仅适用于可变序列，即列表），会出现一些微妙之处。内部计数器用于跟踪下一个要使用的项目，并在每次迭代中递增。当此计数器达到序列的长度时，循环终止。这意味着如果代码块删除了当前（或先前的）项，则下一个项将被跳过（因为它获取了已经处理过的当前项的索引）。同样，如果代码块在当前项之前在序列中插入一个项，则下次循环时当前项将再次被处理。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接