Chapter-7 CombinatorialMathematics 第7章 组合数学 - FullPermutation 全排列
优质
小牛编辑
130浏览
2023-12-01
问题
求拥有(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!))。