排列树理论

  虽然说实际开发中输出所有排列的需求很少，但是一旦有这种需求的时候，临时去想算法还是需要花蛮长时间的。在写代码之前，我们要分析排列是一个什么样子。
  算法和数据结构玩久了，就想都不用想，这是一棵树。

  组成这棵树，好处是不仅可以生成全排列，还可以生成部分排列。但是用这种算法生成的全排列不是最高效的算法。

递归法代码

def recursive_visit(remain_array, result, current_array, num):
    """
    :param remain_array: 剩余数组
    :param current_array: 当前数组
    :param num: 取多少个元素
    :param result: 结果
    :return:
    """
    if num == 0:
        result.append(current_array)
        return

    for i, x in enumerate(remain_array):
        copy = remain_array[:]
        copy.pop(i)
        recursive_visit(copy, result, current_array + [x], num - 1)


def permutations(array, n):
    result = []
    recursive_visit(array, result, [], n)
    return result


if __name__ == '__main__':
    result = permutations(['A', 'B', 'C', 'D'], 2)
    for x in result:
        print(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  测试结果：

['A', 'B']
['A', 'C']
['A', 'D']
['B', 'A']
['B', 'C']
['B', 'D']
['C', 'A']
['C', 'B']
['C', 'D']
['D', 'A']
['D', 'B']
['D', 'C']

1
2
3
4
5
6
7
8
9
10
11
12
13

非递归代码

def recursive_visit(remain_array, result, current_array, num):
    """
    :param remain_array: 剩余数组
    :param current_array: 当前数组
    :param num: 取多少个元素
    :param result: 结果
    :return:
    """
    if num == 0:
        result.append(current_array)
        return

    for i, x in enumerate(remain_array):
        copy = remain_array[:]
        copy.pop(i)
        recursive_visit(copy, result, current_array + [x], num - 1)


def permutations(array, n):
    result = []
    stack = [(array, [], n)]
    while len(stack) > 0:
        remain, current, n = stack.pop()
        if n == 0:
            result.append(current)
            continue

        for i, x in enumerate(remain):
            copy = remain[:]
            copy.pop(i)
            stack.append((copy, current + [x], n - 1))
    return result


if __name__ == '__main__':
    result = permutations(['A', 'B', 'C', 'D'], 2)
    for x in result:
        print(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

  测试结果：

['D', 'C']
['D', 'B']
['D', 'A']
['C', 'D']
['C', 'B']
['C', 'A']
['B', 'D']
['B', 'C']
['B', 'A']
['A', 'D']
['A', 'C']
['A', 'B']
1
2
3
4
5
6
7
8
9
10
11
12

全排列算法

  上述的排列树算法虽然也适用于全排列。但是全排列有更好的算法，这个算法就是大名鼎鼎的Heap算法Heap’s algorithm。注意，这里的Heap不是堆的意思，而是计算机科学家B. R. Heap的姓氏。
  Heap算法是一种递归算法。他的想法就是用互换生成整个凯莱图。其基本算法是这样的，先把前n-1项使用递归方法去互换。一系列互换完成，再与最后一个元素互换。具体的置换原理非常复杂，网上没有讲清楚的，我这次多用几张图画清楚吧，先看看位置变化：

  上面的图什么意思呢？在减号前面是进入节点时的排列，减号后面是程序流程离开节点后的排列。
  这很难看出规律，如果知道置换知识可能更容易理解。我们改成置换表达式再看看：

  在置换图里，因为下层递归完成后，会再执行一次置换，而这次置换会影响同级的下一个节点，所以我把置换放入了平级箭头上。因为最后还执行了一次(1 3)，所以我画了一个自环。我们知道对于3个元素的置换，(1 2)与(1 3)交替就可以遍历完，这在凯莱图里是一个六边形。三元素的置换不足以剖析Heap算法的精妙之处。

  上面的图里我省略了自环。接下来我重点讲讲为什么奇偶处理不一样。
  Heap算法是先处理子节点，再进行一次互换。这样做的目的是为了跳入下一个陪集。每一棵奇数层子树（比如3个元素的置换）都是一个右陪集。但是为什么奇数层和偶数层不一样呢？因为偶数层的最后一个操作，是恒等置换，所以会影响到上一层。举个例子。最底层的子树执行了一个(1 2)互换。但是没有再执行一个(1 2)互换还原。所以这个操作的影响就向上面的奇数层传递了。
  如果奇数层使用(1 3)和(2 3)的交替，那么就变成了$(12)(13)(12)(23)(12)=(12)$，然后这个(1, 2)又传递到上一层，无比混乱。不仅是无比混乱，事实上会产生重复的置换，一旦重复就不能遍历所有的置换了。但如果奇数层一直使用(1 3)的话，就变成了$(12)(13)(12)(13)(12)(13)=e$。这样的话，每个奇数层在顶点得到了还原，而奇数层的子树就形成了一个完整的陪集。
  总而言之，因为奇数层被带入了偶数层遗留的一个置换，所以每次都要执行$(1n)$置换，这样在递归结束后还原为恒等置换。而偶数层在处理结束后会留下一个置换，让奇数层“奇奇得偶”。
  知道了原理，也就能体会Heap算法在叶子上产生所有置换的算法之美，代码也非常容易实现。

Heap算法实现

def recursive(array, last, result):
    if last == 0:
        result.append(array[:])
        return

    for i in range(0, last + 1):
        recursive(array, last - 1, result)
        before = array[:]
        if last & 1 == 0:
            array[0], array[last] = array[last], array[0]
        else:
            array[i], array[last] = array[last], array[i]


def permutations(array):
    result = []
    recursive(array, len(array) - 1, result)
    return result


if __name__ == '__main__':
    result = permutations(['A', 'B', 'C', 'D'])
    for x in result:
        print(x)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

  测试结果：

['A', 'B', 'C', 'D']
['B', 'A', 'C', 'D']
['C', 'A', 'B', 'D']
['A', 'C', 'B', 'D']
['B', 'C', 'A', 'D']
['C', 'B', 'A', 'D']
['D', 'B', 'C', 'A']
['B', 'D', 'C', 'A']
['C', 'D', 'B', 'A']
['D', 'C', 'B', 'A']
['B', 'C', 'D', 'A']
['C', 'B', 'D', 'A']
['D', 'A', 'C', 'B']
['A', 'D', 'C', 'B']
['C', 'D', 'A', 'B']
['D', 'C', 'A', 'B']
['A', 'C', 'D', 'B']
['C', 'A', 'D', 'B']
['D', 'A', 'B', 'C']
['A', 'D', 'B', 'C']
['B', 'D', 'A', 'C']
['D', 'B', 'A', 'C']
['A', 'B', 'D', 'C']
['B', 'A', 'D', 'C']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24