Chapter-7 CombinatorialMathematics 第7章 组合数学 - PermutationGroup 置换群
问题
长度为(n)的序列(s = [x0, x_1, x_2, cdots, 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 = [y0, y_1, y_2, cdots, 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))。