首页 > Python算法 > 回溯算法 阅读数:30

排列组合—回溯算法经典例题

排列问题为:从给定个数的元素中取出指定个数的元素进行排序输出。组合问题为:在 n 个不同的数字中挑选 m 个数字,并将所有的组合方式输出。这两个问题是经典的回溯算法问题。我们首先来解决排列问题,再来解决组合问题。

假设我们需要排列 [1,3,4,5] 这四个数字。我们知道第一个数字有 4 个选择,第二个数字有 3 个选择,第三个数字有 2 个选择,第四个数字有 1 个选择。如果不用回溯算法,其实我们也可以写出代码,伪代码如下:
nums = [1,3,4,5]
for a in nums:
    nums1 = nums without a
    solution1 = [a]
    for b in nums1:
        nums2 = nums1 without b
        solution2 = solution1.append(b)
        for c in nums2:
            nums3 = nums2 without c
            solution3 = solution2.append(c)
            for d in nums3:
                solution4 = solution3.append(c)
                print(solution4)

以上伪代码的思路为:把已经用过的选择从列表中剔除,然后继续利用 for 循环遍历下一个位置的数。这样做的缺点一是代码太累赘,二是写代码之前需要提前知道 nums 的长度。如果用回溯算法来解决这个问题就不会存在这样的缺点。

我们将定义 permute(nums) 方法。输入nums 数组,permute(nums) 方法输出 nums 里数字的所有排列方式。比如 permute([1,2,3]) 输出:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


permute(nums) 方法的思路如下:
  1. 选择第一个位置上的数字,称之为 x;
  2. 利用 permute(nums) 方法得到剩余数字的所有排列方式;
  3. 把 x 放入这些数组的第一个位置。保存答案;
  4. 回到第一步,改变 x;
  5. 尝试过所有x后输出答案。

permute(nums) 方法的边界条件为,如果 nums 数组为空,那么将当前的排列方式加入结果集合并返回。

以 [1,2,3,4] 为例。
  1. 初始时,我们只关心第一个位置的数,它一共有 4 个选择。我们遍历这四种选择,第一次的时候我们会选择 1。
  2. 我们知道从 1 开始的排列组合等于 1+“[2,3,4] 的排列组合”。这时,我们再次调用 permute(nums) 方法,传入 [2,3,4] 就能得到“[2,3,4] 的排列组合”。
  3. 得到 6 个“[2,3,4] 的排列组合”后,将 1 加入数组,放在第一个位置。
  4. 回到第一步,把第一个位置上的数换成 2。

递归步骤如图 1 所示,第一次递归到底层时被保存的组合是[1,2,3,4]。我们来看一下这之后的步骤。
第一个结果
图 1:第一个结果

如图 2 所示,我们返回到第三层。在第三层,我们有两个选项,3 和 4 。我们已经尝试过 3,现在轮到 4。我们将 4 放到第三个位置上,然后将剩下的数字 3,当作参数传入第四层,这时我们得到第二个排列组合 [1,2,4,3]。
第二个结果
图 2:第二个结果

如图 3 所示,我们再次返回到第三层。因为第三层的两个选项——3 和 4,都已经被尝试过了,所以继续后退到第二层。第二层的选项有 2,3,4,我们从 3 继续尝试,将 3 放在第三个位置上。将剩余的数字——2 和 4,传入第三层。然后,将 2 放在第三个位置上,将 4 传入第四层。我们得到的第三个结果是 [1,3,2,4]。
第三个结果
图 3:第三个结果

重复以上的步骤,我们会依次得到 [1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],…,[4,3,2,1]。

排列问题代码:
#排序nums并返回所有组合
def permute(nums,solution = []):
    if not nums:              #边界条件
        res.append(solution)
        return               #返回
    for i in range(len(nums)):
        newSolution = solution + [nums[i]] #依次将nums里的数字放置排列组合的下一个位置上
        newList = nums[0:i]+nums[i+1:]   #newList里是除了nums[i]以外的全部数字
        permute(newList, newSolution)    #继续排列newList里的数字
res = []
permute([1,2,3,4])
solution 是当前排列组合。初始时,solution=[]。放置第一个数字后,solution=[1],放置第二个数字后,solution=[1,2]。

需要注意的是,solution 这个变量只存活在当前层。比如,当我们从第一层递送到第二层的时候,第二层的 solution 和第一层 solution 虽然叫同一个名字,但不是同一个变量。当第二层的 solution 等于 [1,2] 的时候,第一层的 solution 仍然是 [1]。主动变化的是 newSolution,也就是被传入下一层的数组。

如图 4 所示,每一层的 newSolution 都是下一层的 solution。
solution与newSolution的关系
图 4:solution 与 newSolution 的关系

例如,当我们从第四层返回到第三层后,第三层的 solution 不变,还是 [1,2],但是第三层的 for 循环将 newSolution 变为 [1,2,4]。

虽然在图 4 中没有表示,但是当我们再次递归到第四层时,第四层会舍弃原来的 solution 和 newSolution,重新在内存里声明一个叫 solution 的变量和一个叫 newSolution 的变量,然后赋值 solution为[1,2,4]。每一次递进,我们都会重新创立变量并且赋予它们新值。但每一次后退,因为方法没变,所以变量不变。

因为 solution 是“一次性”的变量,所以我们不用去深度复制 solution 再把它加入结果列表,直接利用 append() 方法就可以。同样的道理,每一层的 nums 都是只存在于当前层。当我们在层与层之间递归时,每一层的 nums 都是独立存在的,改变的是 newList。newList 决定下一层的 nums 是什么,只有当 newList 改变并且方法重新递送到下一层的时候,nums 才会改变。

接下来解决组合问题。假定我们需要从 [1,2,3,4] 中选择 2 个数字。我们知道一共有 6 种选择:[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]。

我们将定义 combination(nums) 方法。输入 nums 数组,combination() 方法输出 nums 里数字的所有排列方式。比如 permute([1,2,3,4]) 输出 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。

排列问题和组合问题的性质十分类似。在组合问题中,我们同样可以只关心第一个数字,然后让递归方法去得到剩余数字的组合。

步骤如下:
  1. 选择第一个位置上的数字,称之为 x。
  2. 利用 combination() 方法得到剩余数字的组合。
  3. 把 x 放入第二步得到的数组的第一个位置。保存答案。
  4. 回到第一步,改变 x。
  5. 尝试完所有x后输出答案。

如果传入 combination() 方法的 nums 数组为空,停止递归,将当前的排列方式加入结果集合。

比如,在第一步,我们只关心在 [1,2,3,4] 中选择一个数字,这一共有 4 个选择,当选择 1 的时候,我们知道答案等于 1 加上“[2,3,4] 中选择 1 个数字的组合”,同样的,当我们选择第一个数字为 2 的时候,答案等于 2 加上“[1,3,4] 中选择 1 个数字的组合”。

combination() 方法与 permute() 方法不同的一点在于第二步“剩余数字”的定义。permute() 方法中,“剩余数字”为除了 x 的所有数字。但是,在 combination() 方法中“剩余数字”为 x 之后的所有数字。比如,如果 nums 为 [1,2,3,4],当前数字为 2,那么 permute() 方法的“剩余数字”为 [1,3,4],但 combination() 方法的“剩余数字”为 [3,4]。

这是因为已经用过的数字在组合问题里就不能再用了。在排列问题中,数字的位置有意义,但是组合问题中数字的位置没有意义。比如,[2,1] 和 [1,2] 是两个不同的排列方式,但却是同一个组合。

代码如下:
#nums是待组合的数字列表,solution是当前组合,n是选择的数字数量
#输出所有组合方式
def combination(nums,solution,n):
    if n==0:                #边界条件
        res.append(solution)
        return
    for i in range(len(nums)):
        newSolution = solution + [nums[i]] #依次将nums里的数字放入新组合newSolution
        newList = nums[i+1:]          #剩余数字
        combination(newList, newSolution,n-1)  #在剩余的数字选择n-1个数字
res = []
combination([1,2,3,4,5],[], 3)

运行代码,结果如下:

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]


组合问题的代码与排列问题代码不同的地方有以下两点。
  1. combination() 方法多了一个参数 n,用来表示我们需要选择几个数字。每一次 combination() 方法调用自己的时候,n 都减 1。
  2. newList 的定义不再是 nums[0:i]+nums[i+1:],而是 nums[i+1:]。这是因为我们不能够重复利用已经用过的数字。我们走一遍代码来理解为什么这样定义 newList。

我们第一次进入 combination()方法。combination()的参数为:nums=[1,2,3,4],solution=[],n=2。
for i in range(n):             #n=2,i=0
    newSolution = solution + [nums[i]]   #newSolution = [] + [1] = [1]
    newList = nums[i+1:]          #newList = [2,3,4]
    combination(newList, newSolution, n-1) #combination([2,3,4], [1], 1)
目前选择了一个数字——1,接下来在 [2,3,4] 中选择 1 个数字。

第二次进入 combination() 方法。combination() 的参数为:nums=[2,3,4],solution=[1],n=1。
for i in range(n):             #n=1,i=0
    newSolution = solution + [nums[i]]   #newSolution = [1]+[2]
    newList = nums[i+1:]          #newList = [3,4],而不是[1,3,4]
    combination(newList, newSolution, n-1) #combination([3,4], [1,2], 0)
当前数字是 2。目前选择的两个数字是 1 和 2。newList 是 [3,4 ]而不是 [1,3,4]。如果是 [1,3,4] 的话,逻辑上会说不通,因为 1 已经在组合里了,所以不再是可选项。

第三次进入 combination() 方法。combination() 方法获取的参数为:nums=[3,4],solution=[1,2],n=0。
if n==0:             #n=0
    res.append(solution)      #res = [[1,2]]
    return
满足边界条件,将当前组合加入 res 列表。回到上一次调用 combination() 方法的地方。

combination() 方法当前参数为:nums=[2,3,4],solution=[1],n=1。

继续没有走完的主循环。
for i in range(n):       #n=1,i = 1
    newSolution = solution + [nums[i]] # newSolution = [1]+[3]
    newList = nums[i+1:]     #newList = [4],而不是[1,2,4]
    combination(newList, newSolution, n-1) # combination([4], [1,3], 0)
当前数字是 3。目前选择的两个数字是 1 和 3。newList 是 [4] 而不是 [1,2,4]。因为 4 已经在组合里了,所以不再是可选项。

可以看到,newList 只选取当前数字之后的数字,是因为之前的数字都已经被用过了,而在组合问题中一个数字不能被二次利用。