在给定大小为n的列表中查找2^(n-1)个连接列表
我在 Python 中遇到一个问题：给定一个包含 n 个元素的列表，我想在列表中找到所有“连接”的元素组合。例如，给定list = ['a', 'b', 'c']，我想找到
['a', 'b', 'c']
['ab', 'c']
['a', 'bc']
['abc']
同样，给定list = ['a', 'b', 'c', 'd']，我想找到
['a', 'b', 'c', 'd']
['a', 'bc', 'd']
['a', 'b', 'cd']
['a', 'bcd']
['ab', 'c','d']
['ab', 'cd']
['abc', 'd']
['abcd']
给定一个包含 n 个元素的列表，将有 2^(n-1) 种组合。请问是否有任何提示可以帮助我解决这个问题？我应该使用递归吗？
回答
递归通常是最容易实现的。这是一个可以实现这一点的生成器函数：
def connect(lst):
if not lst:
yield []
for i in range(1, len(lst) + 1):
prefix = ''.join(lst[:i])
for suffix_con in connect(lst[i:]):
yield [prefix] + suffix_con
该方法采用str.join列表的任何ed 前缀，并将其与从相应后缀递归获得的每组连接组合。
>>> list(connect(['a', 'b', 'c']))
[['a', 'b', 'c'], ['a', 'bc'],
['ab', 'c'],
['abc']]
>>> list(connect(['a', 'b', 'c', 'd']))
[['a', 'b', 'c', 'd'], ['a', 'b', 'cd'], ['a', 'bc', 'd'], ['a', 'bcd'],
['ab', 'c', 'd'], ['ab', 'cd'],
['abc', 'd'],
['abcd']]