创建一个嵌套递归列表而不使用切片

Question

我需要编写一个函数，接收一个非负整数并返回：

[] for n=0 

[[]] for n=1 

[[],[[]]] for n=2

[[],[[]],[[],[[]]]] for n=3

等等。对于一个 n，我们将会收到一个大小为 n 的列表，使得在索引 i 上，将有来自列表的所有 i-1 个元素。我不知道如何更好地解释，英语不是我的母语。

我不允许使用列表切片或循环，并且我应该创建每个列表的深层副本，而不使用 copy 模块。我不允许让两个不同的列表或索引指向内存中的同一个列表。

这是我尝试过的：

def list_seq(x, outer_list=[]):
    if x == 0:
        return []
    outer_list.append(list_seq(x-1,outer_list))
    return outer_list

执行 print(list_seq(2)) 的输出结果为 [[], [...]]。

- MadaBit

---

我应该创建每个列表的深拷贝，这是否意味着您不应该缓存递归调用的结果？在这种情况下，复杂度将非常高。 - tobias_k

@tobias_k 我们不允许两个不同的列表或索引指向内存中的同一列表。 - MadaBit

你尝试了什么？ - PApostol

你是否考虑用C++创建解决方案来解决你的问题？ - Vadim Chernetsov

@MadaBit 你为什么撤回了你的代码尝试？没有它，这个问题就不是主题了。 - ggorlen

Answer 1

您可以使用简单的列表推导式将其编写为递归函数：

def f(n):
    return [f(i) for i in range(n)]

或者，你也可以使用 map 代替列表推导式:

def f(n):
    return list(map(f, range(n)))

请注意，如果没有进行缓存，这段代码很快就会变得非常慢。但请注意保留 caching。

- tobias_k

---

抱歉，忘了提到我不能使用循环。 - MadaBit

@MadaBit 那就用 return [*map(f, range(n))] 吧？ - no comment

Answer 2

如果您无法使用循环，可以使用以下方法：

def recursive_list(n):
    if n == 0:
        return []
    else:
        return recursive_list(n-1) +  [recursive_list(n-1)]

编辑

如果您想使用 append，可以执行以下操作：

def recursive_list(n: int) -> list:
    if n:
        result = recursive_list(n-1)
        result.append(recursive_list(n-1))
        return result
    return []

注意：正如评论中指出的那样，缓存会引入一些引用问题，因此我已经删除了缓存版本。

- Sayandip Dutta

---

这是一个很棒的解决方案。非常感谢。可以用append方法代替+吗？或者用一个帮助函数。 - MadaBit

使用 append 添加了一个解决方案。 - Sayandip Dutta

使用 functools.cache 会破坏两个递归调用而不是一个的整个目的。考虑：l = recursive_list(4); print(l); [[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]; l[1].append('oops'); print(l); [[], [[], 'oops'], [[], [[], 'oops']], [[], [[], 'oops'], [[], [[], 'oops']]]] - Stef

@Stef 公平。我只是确保列表不是自包含的。我没有考虑 OP 是否计划在列表之间添加，这是我的疏忽。考虑到 OP 不能使用切片、复制或循环，我不确定结果是否可以被缓存。即使有一些自定义缓存函数，也需要一些机制来复制列表。 - Sayandip Dutta

Answer 3

一种更短的递归解决方案，没有循环：

def l_list(n):
  def f(c, d = []):
     return d if c == n else f(c+1, d+[l_list(c)])
  return f(0)

print(l_list(0))
print(l_list(1))
print(l_list(2))
print(l_list(3))

输出：

[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]

- Ajax1234

Answer 4

还有一个想法，我认为它符合所有规则/要求:

def f(n):
    a = []
    exec('a.append(1 * a);' * n)
    return eval(repr(a))

演示用法：

for n in range(5):
    print(f(n))

输出：

[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]
[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]

- no comment

---

好主意，但实现起来有点可怕。为什么不只是 for _ in range(n): a.append(list(a)) 然后 return a？ - tobias_k

@tobias_k 因为问题中提到了“我不允许使用列表切片或循环”。 - no comment

@tobias_k 还有因为它的“我不允许两个不同的列表或索引指向同一个内存列表”。 - no comment

@tobias_k 它不行 - no comment