<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)