关于算法:搜索算法系列-广度优先搜索

此篇文章应用广搜解决全排列问题，我的上一篇文章具体介绍了应用深搜解决全排列问题的办法。

全排列问题

给定一个 没有反复数字 的序列，返回其所有可能的全排列。例如对于数列 [1, 2, 3] 其全排列为[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。

事实上，在网络上查找全排列问题解决方案，失去的绝大部分答案是应用深度优先搜寻解决的，因为相较于广度优先搜寻而言，深度优先搜寻更容易被了解，下图即深度优先搜寻的示意图。

为了摸索广度优先搜寻，咱们须要借助另一张图片，思考如何实现如图所示的按层遍历？

咱们应用队列数据结构来实现广度优先搜寻，初始将 [1]，[2]，[3] 入队。

思考以后节点为 [1] 的状况：将 [1] 从队列的头部弹出，遍历 nums 数组，寻找排列中的第二个数字。易得在 nums = [1,2,3]中，2 与 3 能够作为排列中的第二个数字。于是 [1,2]，[1,3] 入队。

持续思考以后节点为 [2]，[3] 的状况，直至 [1,2]，[1,3]，[2,1]，[2,3]，[3,1]，[3,2] 全副入队。

接着弹出队列头部 [1,2]，遍历 nums 数组，寻找排列中的第三个数字，于是[1,2,3]，[1,3,2] 入队 … 直到最初一个三位排列 [3,2,1] 入队，全副排列寻找结束。

代码实现如下。

def solution(nums):
    queue = [[i] for i in nums]
    ans = [nums]    # 防止 nums 只有一个元素的状况，与上面 tmp not in ans 响应
    while queue:
        status = queue.pop(0)
        for i in nums:
            if i in status:
                continue
            tmp = status + [i]
            if len(tmp) == len(nums) and tmp not in ans:
                ans.append(tmp)
            else: queue.append(tmp)
    return ans

print solution([1,2,3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

试着打印 solution 函数的中间状态，领会该迭代办法被称作 广度优先搜寻 的起因。

本文示例题目与 leecode 46. 全排列统一，读者可自行尝试提交，验证本人代码的正确性。