Python: 将深度优先搜索转换为广度优先搜索列表的所有组合
Python: Convert a depth first search to a breadth first search for all combinations of a list
我有一个简单的递归函数，它提供对选项列表的每个可能组合的深度优先搜索：
def twoCharacters_dfs(options, used):
for i in range(len(options)):
used.append(options.pop(0))
print("used=", used)
twoCharacters_dfs(options, used)
if len(used) == 0:
return
options.append(used.pop())
twoCharacters_dfs(['q', 'w', 'e', 'r'], [])
输出（由于长度而缩短）如下所示：
used= ['q']
used= ['q', 'w']
used= ['q', 'w', 'e']
used= ['q', 'w', 'e', 'r']
used= ['q', 'w', 'r']
used= ['q', 'w', 'r', 'e']
used= ['q', 'e']
used= ['q', 'e', 'r']
used= ['q', 'e', 'r', 'w']
used= ['q', 'e', 'w']
used= ['q', 'e', 'w', 'r']
....
used= ['w']
....
used= ['e']
....
used= ['r']
....
这一切都很好，并且按我想要的方式工作。但我有兴趣将其从深度优先转换为广度优先，因此输出看起来更像：
used= ['q']
used= ['w']
used= ['e']
used= ['r']
used= ['q', 'w']
used= ['q', 'e']
used= ['q', 'r']
used= ['w', 'q']
used= ['w', 'e']
used= ['w', 'r']
....
我已经有点能力（只有硬编码的固定长度列表）迭代地完成它，但需要一个递归解决方案，以便它可以适用于任何长度的选项。我也有意避免 python 提供我寻求的功能的库，因为我想了解事物的工作原理并构建我自己的东西作为学习练习。
我觉得有一个简单的解决方案，但我无法将广度优先算法概念化到我的代码中。
更新
在尝试递归 BFS 解决方案之前，我想创建一个迭代 BFS 解决方案，因为它似乎更容易实现。事实证明，我也很难做到这一点。
def twoCharacters_bfs_iterative(options, used):
for option in options:
print("using option = ", option)
for option1 in options:
list2 = options[:]
list2.remove(option1)
for option2 in list2:
print("using option = ", option1, option2)
for option1 in options:
list2 = options[:]
list2.remove(option1)
for option2 in list2:
list3 = list2[:]
list3.remove(option2)
for option3 in list3:
print("using option = ", option1, option2, option3)
这实现了我想要的输出（上面列出的），但只适用于我知道长度的集合。我想将它扩展为任意长度的列表，但这样做有困难。我想如果我能让迭代解决方案工作，递归解决方案也不远了。
编辑：我没有从示例中注意到所有排列都是必需的。遵循一个使用列表作为队列的函数：
def bfs(options):
queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
while len(queue) > 0:
head, tail = queue[0]
print(head)
queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
del queue[0]
工作原理如下（64 行，截断）：
>>> bfs(['q','w','e','r'])
['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
...
['r', 'w']
['r', 'e']
['q', 'w', 'e']
['q', 'w', 'r']
['q', 'e', 'w']
...
['r', 'q', 'e', 'w']
['r', 'w', 'q', 'e']
['r', 'w', 'e', 'q']
['r', 'e', 'q', 'w']
['r', 'e', 'w', 'q']
此外，
def bfs(options):
queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
for head, tail in queue:
queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
return [head for head, tail in queue]
这个版本returns一个列表而不是打印。
沿用之前的答案，不考虑排列:
正如其他人在评论中所说，这不自然。遵循 "recursive" 函数：
def bfs(options, level=0):
if level == 0:
for c in options:
print([c])
for i in range(1,len(options)):
bfs(options, i)
else:
for i,c in enumerate(options):
for j,g in enumerate(options[i+1:]):
if i+1+j+level <= len(options):
print([c,*options[i+1+j:i+1+j+level]])
最后一行的 * 需要 Python3，但您可以删除它。
预期输出为：
['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
['q', 'r']
['w', 'e']
['w', 'r']
['e', 'r']
['q', 'w', 'e']
['q', 'e', 'r']
['w', 'e', 'r']
['q', 'w', 'e', 'r']
另一个版本：
def bfs(options, level=0):
for i,c in enumerate(options):
for j,g in enumerate(options[i+1:]):
if i+1+j+level <= len(options):
print([c,*options[i+1+j:i+1+j+level]])
if level == 0:
break
if level < len(options):
bfs(options, level + 1)
我正在 post 回答我自己的问题，以提供有关深度优先搜索和广度优先搜索的一些清晰信息。我最初的目标是我的递归深度优先函数的递归广度优先版本。这是由于对 DFS 和 BFS 之间的根本区别缺乏理解：DFS 使用堆栈而 BFS 使用队列。 （感谢@Patrick Haugh 的见解以及此 post：Performing Breadth First Search recursively）。
DFS 使用堆栈这一事实非常适合递归函数，因为您可以将调用堆栈用作操作堆栈。但这不适用于 BFS 的队列样式。广度优先搜索可以递归完成，但最终有点像深度优先搜索。将 BF 保留为迭代函数会更加清晰和直观。
从不喜欢 copy/pasting 代码而不理解其工作原理，@Matteo T. 正确答案引导我使用我目前正在实施的不带枚举的迭代 BFS 解决方案：
def bfs_iterative(options):
queue = [[item] for item in options]
while queue:
using = queue.pop(0)
print(using)
remaining = [item for item in options if item not in using]
extension = []
for item in remaining:
using.append(item)
extension.append(using[:])
using.pop()
queue.extend(extension)
我有一个简单的递归函数，它提供对选项列表的每个可能组合的深度优先搜索：
def twoCharacters_dfs(options, used):
for i in range(len(options)):
used.append(options.pop(0))
print("used=", used)
twoCharacters_dfs(options, used)
if len(used) == 0:
return
options.append(used.pop())
twoCharacters_dfs(['q', 'w', 'e', 'r'], [])
输出（由于长度而缩短）如下所示：
used= ['q']
used= ['q', 'w']
used= ['q', 'w', 'e']
used= ['q', 'w', 'e', 'r']
used= ['q', 'w', 'r']
used= ['q', 'w', 'r', 'e']
used= ['q', 'e']
used= ['q', 'e', 'r']
used= ['q', 'e', 'r', 'w']
used= ['q', 'e', 'w']
used= ['q', 'e', 'w', 'r']
....
used= ['w']
....
used= ['e']
....
used= ['r']
....
这一切都很好，并且按我想要的方式工作。但我有兴趣将其从深度优先转换为广度优先，因此输出看起来更像：
used= ['q']
used= ['w']
used= ['e']
used= ['r']
used= ['q', 'w']
used= ['q', 'e']
used= ['q', 'r']
used= ['w', 'q']
used= ['w', 'e']
used= ['w', 'r']
....
我已经有点能力（只有硬编码的固定长度列表）迭代地完成它，但需要一个递归解决方案，以便它可以适用于任何长度的选项。我也有意避免 python 提供我寻求的功能的库，因为我想了解事物的工作原理并构建我自己的东西作为学习练习。
我觉得有一个简单的解决方案，但我无法将广度优先算法概念化到我的代码中。
更新
在尝试递归 BFS 解决方案之前，我想创建一个迭代 BFS 解决方案，因为它似乎更容易实现。事实证明，我也很难做到这一点。
def twoCharacters_bfs_iterative(options, used):
for option in options:
print("using option = ", option)
for option1 in options:
list2 = options[:]
list2.remove(option1)
for option2 in list2:
print("using option = ", option1, option2)
for option1 in options:
list2 = options[:]
list2.remove(option1)
for option2 in list2:
list3 = list2[:]
list3.remove(option2)
for option3 in list3:
print("using option = ", option1, option2, option3)
这实现了我想要的输出（上面列出的），但只适用于我知道长度的集合。我想将它扩展为任意长度的列表，但这样做有困难。我想如果我能让迭代解决方案工作，递归解决方案也不远了。
编辑：我没有从示例中注意到所有排列都是必需的。遵循一个使用列表作为队列的函数：
def bfs(options):
queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
while len(queue) > 0:
head, tail = queue[0]
print(head)
queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
del queue[0]
工作原理如下（64 行，截断）：
>>> bfs(['q','w','e','r'])
['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
...
['r', 'w']
['r', 'e']
['q', 'w', 'e']
['q', 'w', 'r']
['q', 'e', 'w']
...
['r', 'q', 'e', 'w']
['r', 'w', 'q', 'e']
['r', 'w', 'e', 'q']
['r', 'e', 'q', 'w']
['r', 'e', 'w', 'q']
此外，
def bfs(options):
queue = [([c], [*options[:i], *options[i+1:]]) for i,c in enumerate(options)]
for head, tail in queue:
queue.extend([([*head, c], [*tail[:i], *tail[i+1:]]) for i,c in enumerate(tail)])
return [head for head, tail in queue]
这个版本returns一个列表而不是打印。
沿用之前的答案，不考虑排列:
正如其他人在评论中所说，这不自然。遵循 "recursive" 函数：
def bfs(options, level=0):
if level == 0:
for c in options:
print([c])
for i in range(1,len(options)):
bfs(options, i)
else:
for i,c in enumerate(options):
for j,g in enumerate(options[i+1:]):
if i+1+j+level <= len(options):
print([c,*options[i+1+j:i+1+j+level]])
最后一行的 * 需要 Python3，但您可以删除它。
预期输出为：
['q']
['w']
['e']
['r']
['q', 'w']
['q', 'e']
['q', 'r']
['w', 'e']
['w', 'r']
['e', 'r']
['q', 'w', 'e']
['q', 'e', 'r']
['w', 'e', 'r']
['q', 'w', 'e', 'r']
另一个版本：
def bfs(options, level=0):
for i,c in enumerate(options):
for j,g in enumerate(options[i+1:]):
if i+1+j+level <= len(options):
print([c,*options[i+1+j:i+1+j+level]])
if level == 0:
break
if level < len(options):
bfs(options, level + 1)
我正在 post 回答我自己的问题，以提供有关深度优先搜索和广度优先搜索的一些清晰信息。我最初的目标是我的递归深度优先函数的递归广度优先版本。这是由于对 DFS 和 BFS 之间的根本区别缺乏理解：DFS 使用堆栈而 BFS 使用队列。 （感谢@Patrick Haugh 的见解以及此 post：Performing Breadth First Search recursively）。
DFS 使用堆栈这一事实非常适合递归函数，因为您可以将调用堆栈用作操作堆栈。但这不适用于 BFS 的队列样式。广度优先搜索可以递归完成，但最终有点像深度优先搜索。将 BF 保留为迭代函数会更加清晰和直观。
从不喜欢 copy/pasting 代码而不理解其工作原理，@Matteo T. 正确答案引导我使用我目前正在实施的不带枚举的迭代 BFS 解决方案：
def bfs_iterative(options):
queue = [[item] for item in options]
while queue:
using = queue.pop(0)
print(using)
remaining = [item for item in options if item not in using]
extension = []
for item in remaining:
using.append(item)
extension.append(using[:])
using.pop()
queue.extend(extension)