MATLAB 加密群置换,PermutationGroup 置换群

朱雀 2023-01-14 03:59 125阅读 0赞

\# Permutation Group - 置换群

\--------

\#\#\#\# 问题

长度为\\(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\]\\)。

给出长度相同的序列\\(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\]\\\]

求长度为\\(n\\)的序列\\(s\\)在置换原则t下，经过\\(k\\)次置换操作后的元素排列情况。

解法：

暴力\\(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\]

\\\]

\\((1)\\)对于第\\(0\\)个元素，第\\(1\\)次置换后\\(s\[0\] = 6\\)；

\\\[ s\_1 = \[6, 4, 2, 0, 1, 7, 3, 5, 9, 8\] \\\]

\\((2)\\)对于第\\(0\\)个元素，第\\(2\\)次置换后\\(s\[0\] = 3\\)；

\\\[ s\_2 = \[3, 1, 2, 6, 4, 5, 0, 7, 8, 9\] \\\]

\\((3)\\)对于第\\(0\\)个元素，第\\(3\\)次置换后\\(s\[0\] = 0\\)；

\\\[ s\_2 = \[0, 4, 2, 3, 1, 7, 6, 5, 9, 8\] \\\]

\\((4)\\)对于第\\(0\\)个元素，第\\(4\\)次置换后\\(s\[0\] = 6\\)；

\\\[ s\_2 = \[6, 1, 2, 0, 4, 5, 3, 7, 8, 9\] \\\]

我们可以看出第\\(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)。

经过观察发现任意元素\\(s\[i\]\\)都拥有一个循环周期，因此只要确定每个元素的周期，就可以避免暴力循环，直接求出k次置换操作后的序列s。该算法的时间复杂度为\\(O(n)\\)。