Chapter-7 CombinatorialMathematics 第7章 组合数学 - UniqueFullPermutation 唯一的全排列
优质
小牛编辑
117浏览
2023-12-01
问题
求拥有(n)个不同元素的数组(A = [a0,a_1,a_2,…,a{n-1}])的唯一的全排列，其中数组(A)中存在重复的元素。
比如(A = [1, 2, 3_1, 3_2])，其全排列为：
[
[3_2, 3_1, 1, 2]
[3_1, 3_2, 1, 2]
[3_1, 1, 3_2, 2]
[3_1, 1, 2, 3_2]
[3_2, 1, 3_1, 2]
[1, 3_2, 3_1, 2]
[1, 3_1, 3_2, 2]
[1, 3_1, 2, 3_2]
[3_2, 1, 2, 3_1]
[1, 3_2, 2, 3_1]
[1, 2, 3_2, 3_1]
[1, 2, 3_1, 3_2]
[3_2, 3_1, 2, 1]
[3_1, 3_2, 2, 1]
[3_1, 2, 3_2, 1]
[3_1, 2, 1, 3_2]
[3_2, 2, 3_1, 1]
[2, 3_2, 3_1, 1]
[2, 3_1, 3_2, 1]
[2, 3_1, 1, 3_2]
[3_2, 2, 1, 3_1]
[2, 3_2, 1, 3_1]
[2, 1, 3_2, 3_1]
[2, 1, 3_1, 3_2]
]
由于数组(A)中重复的元素，产生的全排列中也存在([1, 2, 3_1, 3_2] [1, 2, 3_2, 3_1])这样重复的排列，但实际上我们只需要一个([1, 2, 3, 3])。因此它的唯一的全排列为：
[
[3, 3, 1, 2]
[3, 1, 3, 2]
[3, 1, 2, 3]
[1, 3, 3, 2]
[1, 3, 2, 3]
[1, 2, 3, 3]
[3, 3, 2, 1]
[3, 2, 3, 1]
[3, 2, 1, 3]
[2, 3, 3, 1]
[2, 3, 1, 3]
[2, 1, 3, 3]
]
解法：
在的基础上。
初始时假设数组(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!))。
Online Judge：