<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Full Permutation - 全排列 -------- #### 問題 <p id="i">求擁有\(n\)個不同元素的數組\(A = [a_0,a_1,a_2,…,a_{n-1}]\)的所有全排列。 </p> 解法： <p id="i">本文介紹Steinhaus-Johnson-Trotter算法。 </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, \dots ,a_{n-1}]\)的全排列。該算法的時間復雜度為\(O(n!)\)。 </p> </div> -------- #### StackOverflow上關于全排列的問題 * [http://stackoverflow.com/questions/9878846/listing-all-permutations-of-a-given-set-of-values](http://stackoverflow.com/questions/9878846/listing-all-permutations-of-a-given-set-of-values) #### Steinhaus-Johnson-Trotter算法 * [https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) #### LeetCode * [leetcode-46](https://leetcode.com/problems/permutations/#/description) * [leetcode-46 source.hpp](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/attachment/leetcode46.hpp) -------- * [Upper Folder - 上一級目錄](../) * [Source Code - 源碼](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/FullPermutation.hpp) * [Test Code - 測試](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/FullPermutation.cpp)