如何平衡此递归函数中的这些括号?

Question

我正在尝试编写一个递归的Python函数，以从给定的数字中获取所有连续的1位或2位数字排序。 例如，给定123，结果将是：[[1, 2, 3], [12, 3], [1, 23]]。

我写了一个似乎在正确轨道上的函数，但我无法平衡括号。

def gen_codes(num):
if len(str(num)) == 1:
return [[num]]
result = []
for i in range(1, 3):
rest_str = str(num)[i:]
path = [int(str(num)[0:i])]
if len(rest_str):            
path = [path + x for x in gen_codes(int(rest_str))]
result.append(path)
return result
print(gen_codes(123))

这输出：

[[[1, [2, 3]], [1, 23]], [[12, 3]]]

预期：

[[1, 2, 3], [12, 3], [1, 23]]

Answer 1

你的问题出在以下行上：

path = [path + x for x in gen_codes(int(rest_str))]

因为它增加了列表的额外嵌套级别。您应该替换此代码：

if len(rest_str):            
path = [path + x for x in gen_codes(int(rest_str))]
result.append(path)

跟

if len(rest_str):
for x in gen_codes(int(rest_str)):
result.append(path + x)
else:
result.append(path)

然后你的代码将产生所需的结果。例如：

print(gen_codes(123))
print(gen_codes(1234))
print(gen_codes(12345))

输出：

[[1, 2, 3], [1, 23], [12, 3]]
[[1, 2, 3, 4], [1, 2, 34], [1, 23, 4], [12, 3, 4], [12, 34]]
[[1, 2, 3, 4, 5], [1, 2, 3, 45], [1, 2, 34, 5], [1, 23, 4, 5], [1, 23, 45], [12, 3, 4, 5], [12, 3, 45], [12, 34, 5]]

Answer 2

可能有更高性能的方法来编写它，但这是我想到的第一个方法：

def f(s: str) -> List[List[int]]:
if len(s) == 1:
return [[int(s)]]
if len(s) == 2:
return [[int(s[0]), int(s[1])], [int(s)]]
return (
[[int(s[0]), *xs] for xs in f(s[1:])] +
[[int(s[0:2]), *xs] for xs in f(s[2:])]
)

两种基本情况：

• 如果s == "a"，则返回[a]
• 如果s == "ab"，则返回[a, b]并[ab]

对于所有其他字符串，

• 如果s == "ab[...]"，则返回[a, *xs] for xs in f(b[...])并[ab, *xs] for xs in f([...])

一个关键思想是始终如一地在正确的(一元(上下文中运作。这总是List[List[int]].如果你退回了其他任何东西，你就做错了什么。