Unique Full Permutation - 唯一的全排列

问题

求拥有(n)个不同元素的数组(A = [a0,a_1,a_2,…,a{n-1}])的唯一的全排列，其中数组(A)中存在重复的元素。

比如(A = [1, 2, 3_1, 3_2])，其全排列为：

由于数组(A)中重复的元素，产生的全排列中也存在([1, 2, 3_1, 3_2] [1, 2, 3_2, 3_1])这样重复的排列，但实际上我们只需要一个([1, 2, 3, 3])。因此它的唯一的全排列为：

在的基础上。

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

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

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

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

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

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

Online Judge：

• leetcode-47
• leetcode-47 source.hpp

• Upper Folder - 上一级目录
• Source Code - 源码
• Test Code - 测试