<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Unique Full Permutation - 唯一的全排列 -------- #### 问题 <p id="i">求拥有\(n\)个不同元素的数组\(A = [a_0,a_1,a_2,…,a_{n-1}]\)的唯一的全排列，其中数组\(A\)中存在重复的元素。 </p> <p id="i">比如\(A = [1, 2, 3_1, 3_2]\)，其全排列为： </p> \[ [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] \] <p id="i">由于数组\(A\)中重复的元素，产生的全排列中也存在\([1, 2, 3_1, 3_2] [1, 2, 3_2, 3_1]\)这样重复的排列，但实际上我们只需要一个\([1, 2, 3, 3]\)。因此它的唯一的全排列为： </p> \[ [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] \] 解法： <p id="i">在<FullPermutation>的基础上。 </p> <p id="i">初始时假设数组\(A = []\)，其全排列只有\(1\)个，即\([]\)本身。 </p> <p id="i">在初始状态的基础上增加新的元素，新的元素可以插入在原数组中的任意位置。例如对于数组\(B = [1, 2, 3]\)，新元素\(x\)可以在\(3\)个元素中选择\(4\)个任意位置插入，得到\(4\)种情况：</p> \[ [x, 1, 2, 3] \\ [1, x, 2, 3] \\ [1, 2, x, 3] \\ [1, 2, 3, x] \] <p id="i">\((1)\)在初始状态\(A = []\)的基础上增加新的元素\(a_0\)，新元素的位置是唯一的，得到\(A = [a_0]\)。得到\(1\)个排列： </p> \[ [a_0] \\ \] <p id="i">\((2)\)在第\((1)\)轮的基础上增加新的元素\(a_1\)，新元素可以插入的位置有\(2\)个，得到的排列有\(2\)个： </p> \[ [a_0,a_1] \\ [a_1,a_0] \] <p id="i">\((3)\)在第\((2)\)轮的基础上增加新的元素\(a_2\)，对于第\((2)\)轮中的每个排列，新元素可以插入的位置都有\(3\)个，得到的排列共有\(2 \times 3 = 6\)个： </p> \[ [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] \] <p id="i">重复上述操作，即可得到长度为\(n\)的数组\(A = [a_0,a_1,a_2, \cdots ,a_{n-1}]\)的全排列。该算法的时间复杂度为\(O(n!)\)。 </p> </div> <br> Online Judge： * [leetcode-47](https://leetcode.com/problems/permutations-ii/) * [leetcode-47 source.hpp](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/attachment/leetcode-47.hpp) -------- * [Upper Folder - 上一级目录](../) * [Source Code - 源码](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/UniqueFullPermutation.hpp) * [Test Code - 测试](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/UniqueFullPermutation.cpp)