问题
包含n个元素的排列s=[x0,x1,x2,…,xn−1],元素范围为[0,n−1]且互不相同。另一个包含n个元素的数组t=[y0,y1,y2,…,yn−1],元素范围也是[0,n−1]且互不相同。且s=t。
排列s在数组t上的置换操作为s[t[i]]=s[i](其中i∈[0,n−1]),称t是s的置换准则。对s中的所有元素按照数组t的对应下标上的值进行置换称为一次置换操作。例如
s=[0,1,2,3,4,5,6,7,8,9] 在置换准则
t=[3,4,2,6,1,7,0,5,9,8] 进行一次置换后得到
s=[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,即s1=[6,4,2,0,1,7,3,5,9,8];
(2) 对于第0个元素,第2次置换后s[0]=3,即s2=[3,1,2,6,4,5,0,7,8,9];
(3) 对于第0个元素,第3次置换后s[0]=0,即s3=[0,4,2,3,1,7,6,5,9,8];
(4) 对于第0个元素,第4次置换后s[0]=6,即s4=[6,1,2,0,4,5,3,7,8,9];
第4次置换后的s4[0]和第1次置换后的s1[0]相同,即s4[0]=s1[0]。可以看出置换操作存在周期性。本题例子中,第0个元素s[0]的置换周期为3,即si+3[0]=si[0](其中i≥0)。
只要确定所有元素的置换周期,就可以跳过k次暴力循环。设m为包含n个元素的排列s上平均每个元素的置换周期,则该算法的时间复杂度为O(n×m)。
源码
PermutationGroup.h
PermutationGroup.cpp
测试
PermutationGroupTest.cpp