数组全排列问题

最近看到剑指offer上一道数组全排列的题目，看似很简单，仔细分析一下，还是有点难以理解，特此在这拆解下，希望能够加深理解。

题目：

给定一个数组，打印出数组的所有排列。比如数组为[1, 2, 3]，那最终输出为：

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

就是把数组的所有顺序的可能都输出出来。

解题思路

1、递归解法

思路

递归的主旨思想就是把问题转化成一个或几个更小规模的子问题，比如说[1, 2, 3]的全排列不好处理，那我们固定第一位是1，然后求[2, 3]的全排列，然后再把第一位固定为2，求[1, 3]的全排列，最后把第一位固定成3，求[1, 2]的全排列。这样，经过层层推演，可以把题目转换成求长度为1的数组的全排列，很显然就得到答案了。

进一步解析

上面的思想是基本没什么问题的，但是怎么实现固定第一位呢，这里有个比较巧妙的方法，就是让第一位分别和后面几位进行交换，这样每个数字都会被固定在第一位一次，然后递归进行后面的操作，注意为了复用当前的数组，而不是每次都进行值拷贝，每次递归执行完了，要把之前的顺序换回来，这样就确保了一个父问题处理多个子问题的时候不会因为某个子问题改变了数组顺序，而无法处理下一个子问题了，具体来看下代码：

def _all_sort(arr: list, start: int, _len: int):
    """
    :param arr: 要全排列的数组
    :param start: 从数组的start位置之后开始全排列
    :param _len: 数组总长度
    """
    for i in range(start, _len):
        # 如果当前全排列已经是最后一位了，则输出数组
        if start == _len - 1:
            print(arr)
        else:
            # 将start位置与各个位置交换
            arr[i], arr[start] = arr[start], arr[i]
            # 交换完start自增1，处理子问题
            _all_sort(arr, start+1, _len)
            # 交换完再换回来，确保每个子问题执行完，不影响父问题的顺序
            arr[i], arr[start] = arr[start], arr[i]

def all_sort(arr: list):
    # 从0位置开始全排列
    start = 0
    _len = len(arr)
    _all_sort(arr, start, _len)

if __name__ == '__main__':
    arr = [1, 2, 4]
    all_sort(arr)

# [1, 2, 4]
# [1, 4, 2]
# [2, 1, 4]
# [2, 4, 1]
# [4, 2, 1]
# [4, 1, 2]

存在重复的问题

上面的代码，在数组没有重复元素的时候运行是正常的，但是一旦有重复就会出现一些小问题，我们看下arr为[1, 2, 2]的执行结果：

# [1, 2, 2]
# [1, 2, 2]
# [2, 1, 2]
# [2, 2, 1]
# [2, 2, 1]
# [2, 1, 2]

发现没，有一些组合是重复的，针对这些情况，需要做一些过滤，拿[1, 2, 2]进行举例，当1和第一个2交换时正常交换，但是当1和第二个2交换的时候就要判定之前之前有没有和2交换过，基于此我们升级一下代码：

def _all_sort(arr: list, start: int, _len: int):
    for i in range(start, _len):
        if start == _len - 1:
            print(arr)
        # 不用和自身交换
        elif i == start:
            _all_sort(arr, start + 1, _len)
        else:
            # 判定当前元素是否重复出现
            is_mutil = False
            for j in range(start, i):
                if arr[j] == arr[i]:
                    is_mutil = True
                    break
            # 如果已经出现过，就不在生成新的子问题了
            if is_mutil is True:
                continue
            arr[i], arr[start] = arr[start], arr[i]
            _all_sort(arr, start+1, _len)
            arr[i], arr[start] = arr[start], arr[i]


def all_sort(arr: list):
    start = 0
    _len = len(arr)
    _all_sort(arr, start, _len)


if __name__ == '__main__':
    arr = [1, 2, 2]
    all_sort(arr)
    print()
    arr = [1, 1, 2, 2]
    all_sort(arr)

通过执行上面的代码，得到结果：

# [1, 2, 2]
# [2, 1, 2]
# [2, 2, 1]
#
# [1, 1, 2, 2]
# [1, 2, 1, 2]
# [1, 2, 2, 1]
# [2, 1, 1, 2]
# [2, 1, 2, 1]
# [2, 2, 1, 1]

这样就成功解决了有重复数据的问题，不过同时也提升了时间复杂度，由nⁿ提升到了n⁽ⁿ⁺¹⁾，可以尝试通过集合来判定有没有重复数据，但是这样会提高程序的空间复杂度，消耗更多的内存，且随着递归层数的增加，这个空间复杂度也会增加。

1、非递归解法

为什么要用非递归算法

很多语言为了解决因代码写错导致递归没有出口的问题，对递归层数都有严格限制的，比如python，当递归层数超过1000的时候，程序就会出错，比如上面的递归方法是无法解决长度为1001的数组的全排列问题的。

思路

把数组当做一个数字，按照从小到大的顺序找，比如数组[1, 2, 3]，我们按照从小到大找全排列，我们找到最小的数字是123，然后次之是132，然后213、321、312、321，这样就找到了数组的所有全排列。
上面的思路怎么实现呢？
首先，通过排序，将数组以升序排列，这样数组表示的数组肯定就是最小的数字了，因为任何2个位置交换，都会导致高位数字变大，低位数字变小，最终整体数字变大。
接下来，我们默认数组是有序的，开始找比当前数字大一点的数字，比如现在是123，那就要通过一定的方式得到132，那我们要怎么做呢，先看下做法，再说明原因：

1、从后往前找，找到当前数字大于后面一位数字就停止查找，并记录当前index，比如2,4,3,1从后往前，当找到2,4的时候就符合条件，把2这个数字记做curr_num，2的位置记做curr_index。

2、找到curr_index后面的数字中所有大于curr_num的数字中的最小数，记做large_min_num，large_min_num的位置记做large_min_index，并将curr_index与large_min_index数字进行交换。比如2,4,3,1，假如这个时候数字2是curr_index，那后面的3,4都比2大，取其中的最小值，就是3，所以large_min_num就是3，然后将2与3交换，就得到序列3,4,2,1。

3、将curr_index之后的数组倒序排列，像上面得到3,4,2,1，3位置后的4,2,1倒序，得到的结果就是3,1,2,4，这个序列就是比2,4,3,1“大一点”的序列，这样不断从当前序列开始迭代，找到大一点的序列，最终，当不能找到比当前序列还大的序列，就停止查找了，这样就找到所有的全排列了。

上面的几步，为了表述方便，下文简称为步骤1、2、3。我们尝试通过这几个步骤找出1,2,3序列的所有全排列：

• 步骤1：找到数字2，步骤2：交换2和3，步骤3：2逆序还是2，最终得到1,3,2；
• 接上面的1,3,2继续找，步骤1：找到数字1，步骤2：交换1和2，步骤3：3,1逆序后是1,3，最终得到序列2,1,3;
• 步骤1：找到数字1，步骤2：交换1和3，步骤3：1逆序后是1，最终得到2,3,1；
• 步骤1：找到数字2，步骤2：交换2和3，步骤3：2,1逆序后是1,2，最终得到3,1,2；
• 步骤1：找到数字1，步骤2：交换1和2，步骤3：1逆序后是1，最终得到3,2,1；
• 步骤1：找不到数字，退出循环。

def all_sort(arr: list):
    tmp_arr = arr.copy()
    tmp_arr.sort()
    _len = len(tmp_arr)
    while 1:
        is_change = False
        print(arr)
        for i in range(_len-2, -1, -1):
            if arr[i] < arr[i+1]:
                swap_num(arr, i)
                reverse_arr(arr, i+1)
                is_change = True
                break

        if is_change is False:
            break


def swap_num(arr: list, index: int):
    length = len(arr)
    num = arr[index]

    compare_start = index + 1
    result = arr[compare_start]
    compare_index = compare_start

    for i in range(compare_start, length):
        if num < arr[i] <= result:
            result = arr[i]
            compare_index = i
    arr[index], arr[compare_index] = arr[compare_index], arr[index]


def reverse_arr(arr: list, start: int):
    left, right = start, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1


if __name__ == '__main__':
    arr = [1, 2, 3, 4]
    all_sort(arr)
# [1, 2, 3, 4]
# [1, 2, 4, 3]
# [1, 3, 2, 4]
# [1, 3, 4, 2]
# [1, 4, 2, 3]
# [1, 4, 3, 2]
# [2, 1, 3, 4]
# [2, 1, 4, 3]
# [2, 3, 1, 4]
# [2, 3, 4, 1]
# [2, 4, 1, 3]
# [2, 4, 3, 1]
# [3, 1, 2, 4]
# [3, 1, 4, 2]
# [3, 2, 1, 4]
# [3, 2, 4, 1]
# [3, 4, 1, 2]
# [3, 4, 2, 1]
# [4, 1, 2, 3]
# [4, 1, 3, 2]
# [4, 2, 1, 3]
# [4, 2, 3, 1]
# [4, 3, 1, 2]
# [4, 3, 2, 1]

我们来看下，为什么这样就能找到比当前数字大一点的数，拿1,4,3,2这个序列举例，从后往前对比，到1,4这个序列停止，定位到1这个位置，因为1后面的几个数字是从大到小排列，所以这个序列为1开头的最大值，所以如果想增大这个值，就要考虑比1大一点的数字开头，然后然后后面的数字升序排列，就可以找到大一点的数字了。比如这个时候1和2替换，序列变成2,4,3,1，发现没，替换之后2后面的数字顺序依然是降序，因为和比自己大一点的数字替换，不会改变后面序列的顺序，这个时候将4,3,1逆序，自然就是升序排列了，也就找到了这个比1,4,3,2大一点的2,1,3,4这个序列，这样不断迭代，每次都找到大一点的序列，最终到4,3,2,1停止，就完成了数组的全排列。