<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Permutation Group - 置換群 -------- #### 問題 <p id="i">長度為\(n\)的序列\(s = [x_0, x_1, x_2, \dots, x_{n-1} ]\)上有\(n\)個數字，每個數字各不相同，且任意的數字都滿足\(\forall x_i \in [0, n-1]\)。例如\(s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\)就是這樣一個長度為\(10\)的序列，擁有\(10\)個各不相同的數字，且每個數字都滿足\(i \in [0, 9]\)。 </p> <p id="i">給出長度相同的序列\(t = [y_0, y_1, y_2, \dots, y_{n-1} ]\)，與序列\(s\)滿足相同的條件（有\(n\)個數字，每個數字各不相同，且任意的數字都滿足\(\forall y_i \in [0, n-1]\)）。例如 \[t = [3, 4, 2, 6, 1, 7, 0, 5, 9, 8]\] 我們將序列\(t\)作為序列\(s\)的置換準則，置換操作可以令\(s[t[i]] = s[i]\)，其中\(i \in [0, n-1]\)。將序列\(s\)中的所有元素按照序列\(t\)中的下標進行一次置換，稱為一次置換操作。例如 \[s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\] 經過序列\(t\)的一次置換后，變成 \[[6, 4, 2, 0, 1, 7, 3, 5, 9, 8]\] </p> <p id="i">求長度為\(n\)的序列\(s\)在置換原則t下，經過\(k\)次置換操作后的元素排列情況。 </p> 解法： <p id="i">暴力\(k\)次循環時間復雜度過高。我們來仔細考察上面例子中的序列\(s\)及其置換準則\(t\)： \[ s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] \\ t = [3, 4, 2, 6, 1, 7, 0, 5, 9, 8] \] <p id="i">\((1)\)對于第\(0\)個元素，第\(1\)次置換后\(s[0] = 6\)； </p> \[ s_1 = [6, 4, 2, 0, 1, 7, 3, 5, 9, 8] \] <p id="i">\((2)\)對于第\(0\)個元素，第\(2\)次置換后\(s[0] = 3\)； </p> \[ s_2 = [3, 1, 2, 6, 4, 5, 0, 7, 8, 9] \] <p id="i">\((3)\)對于第\(0\)個元素，第\(3\)次置換后\(s[0] = 0\)； </p> \[ s_2 = [0, 4, 2, 3, 1, 7, 6, 5, 9, 8] \] <p id="i">\((4)\)對于第\(0\)個元素，第\(4\)次置換后\(s[0] = 6\)； </p> \[ s_2 = [6, 1, 2, 0, 4, 5, 3, 7, 8, 9] \] <p id="i">我們可以看出第\(4\)次置換和第\(1\)置換后\(s[0]\)的結果相同，這說明置換操作是有周期性的，第0個元素\(s[0]\)的周期為3，即\(s[0]_{i+3} = s[0]_{i}\)，其中\(i \in [0, 6]\)。不同元素的周期是不同的，比如\(s[2]\)的周期為1（\(s[2]_{i+1} = s[2]_{i}\)，其中\(i \in [0, 8]\)），因為\(s[2] \equiv 2)。 </p> <p id="i">經過觀察發現任意元素\(s[i]\)都擁有一個循環周期，因此只要確定每個元素的周期，就可以避免暴力循環，直接求出k次置換操作后的序列s。該算法的時間復雜度為\(O(n)\)。</p> </div> * [Upper Folder - 上一級目錄](../) * [Source Code - 源碼](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/PermutationGroup.hpp) * [Test Code - 測試](https://github.com/zhaochenyou/Way-to-Algorithm/blob/master/src/CombinatorialMathematics/PermutationGroup.cpp) --------