全排列，递归与分治

能够用递归和分治解决的，特征都是下一级做的事跟上一级一样（抽象），最后一层做真正的业务。比如n个数字的全排列，抽象出来就是每n-1个数字的全排列

它的难点就在于抽象，因为等于什么都没描述（我要5个数字的全排列，你就说，那好，你告诉我这4个数字的全排列，我就能告诉你5个数字的全排列）。

也就是说，尝试用n和n-1的思维（有点像归纳法，动态规划）去描述问题，而不去看能不能解决。

具体到这里，以ABCD为例，我们的请求过程应该是这样的

• A打头的话，BCD的全排列 swap(0, 0)
• B打头的话，ACD的全排列 swap(0, 1)
• ...swap(0,2)
• ...swap(0,3)

自己是可以数出来的：

A固定，BCD的所有排列 swap(0,0)
  B固定，CD的所有排列 swap(1,1)
      C固定，D的所有排列 swap(1,2)（1）
      D固定，C的所有排列 swap(1,3)（1）
  C固定，同B（2）
  D固定，同B（2）
  计6种
B固定，同A，(6) swap(0,1)
C固定，同A，(6) swap(0,2)
D固定，同A，(6) swap(0,3)
结果应该是24

所有缩进部分都是递归，所以真正的业务代码就是一句话，交换每次比较的数组的第一个和剩下的几个的位置，然后递归下去

ctr = 0
def perm(arr, start=0, end=None):
    global ctr
    end = end or len(arr)

    if start == end:
        print(arr)
        ctr += 1
    else:
        for i in range(start, end):
            # 思路是，我每次只动一个数字，然后固定住这个数字，看剩下的数字有多少种排列
            # 代码里每次把固定的数字挪到开头
            arr[i], arr[start] = arr[start], arr[i]
            perm(arr, start+1, end)
            arr[i], arr[start] = arr[start], arr[i]

if __name__ == "__main__":
    arr = [1,2,3,4]
    perm(arr)
    print(ctr)

output: 24

可能是我理解能力的问题，所有人都没有解释为什么有swap，可能是太直观吧，毕竟swap才是真正在”排列“的业务代码。我还是自己写一遍才想明白，记录一下吧。