Full Permutation - 全排列

求拥有(n)个不同元素的数组(A = [a0,a_1,a_2,…,a{n-1}])的所有全排列。

解法：

本文介绍Steinhaus-Johnson-Trotter算法。

初始时假设数组(A = [])，其全排列只有(1)个，即([])本身。

在初始状态的基础上增加新的元素，新的元素可以插入在原数组中的任意位置。例如对于数组(B = [1, 2, 3])，新元素(x)可以在(3)个元素中选择(4)个任意位置插入，得到(4)种情况：

[
[x, 1, 2, 3] \
[1, x, 2, 3] \
[1, 2, x, 3] \
[1, 2, 3, x]
]

((1))在初始状态(A = [])的基础上增加新的元素(a_0)，新元素的位置是唯一的，得到(A = [a_0])。得到(1)个排列：

[
[a_0] \
]

((2))在第((1))轮的基础上增加新的元素(a_1)，新元素可以插入的位置有(2)个，得到的排列有(2)个：

[
[a_0,a_1] \
[a_1,a_0]
]

((3))在第((2))轮的基础上增加新的元素(a_2)，对于第((2))轮中的每个排列，新元素可以插入的位置都有(3)个，得到的排列共有(2 \times 3 = 6)个：

[
[a_0,a_1,a_2] \
[a_0,a_2,a_1] \
[a_2,a_1,a_0] \
[a_1,a_0,a_2] \
[a_2,a_0,a_1] \
[a_1,a_2,a_0]
]

重复上述操作，即可得到长度为(n)的数组(A = [a0,a_1,a_2, \cdots ,a{n-1}])的全排列。该算法的时间复杂度为(O(n!))。

FullPermutation 全排列