CSDN ·

置换群Larry's Array

置换群Larry's Array

  • HackerRank Larry's Array两种解法
  • 解法一: 冒泡轮换法
  • 解法二: 置换全排序为偶
  • 置换群
  • 置换奇偶性

HackerRank Larry’s Array两种解法

这道题目并不出名，但更巧妙的的思路涉及数学中的置换群。有必要留意一下这方面的理论。

下面是Larray’s Array问题

这道题目需要通过3个数字的若干次轮换操作将原始序列变为有序， 问是否存在这样的操作集合或者序列。

解法一: 冒泡轮换法

容易观察原始序列一定可以将最后2个最大数字之外的数字置换至最终有序数组位置，所以第一种思路是遍历数组，从最小到倒数第三个依次向左移动（置换），最后判断剩余2个数的顺序即可，代码如下。

def sortMin ( arr , i ) : 
 mid = arr [ i : ] . index ( min ( arr [ i : ] ) ) + i
 while i != mid : 
 s = max ( mid - 2 , i ) # mid-2 is the 1th, prev 2 
 a = arr [ s : s + 3 ] 
 a = a [ a . index ( min ( a ) ) : ] + a [ : a . index ( min ( a ) ) ] 
 arr [ s : s + 3 ] = a
 mid = s # arr[i] != s[0] 则继续冒泡 
 
 def larrysArray ( A ) : 
 # Write your code here 
 for i in range ( 0 , len ( A ) - 2 ) : 
 sortMin ( A , i ) 
 return 'YES' if A [ - 2 ] > A [ - 3 ] and A [ - 1 ] > A [ - 2 ] else 'NO'
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

测试结果全部AC, 该解法每步迭代轮换均使得最小值([min(mid-2, i), +2])居前, 分析可知该算法时间复杂度 O ( n 2 ) O(n^2) O ( n 2 ) 另外直观感觉轮换操作序列不唯一，需要探究置换的等价性，利用这种性质（置换奇偶性）判断是否存在合理操作序列.

解法二: 置换全排序为偶

置换群

这里需要引入群论中 置换群 的概念， 置换群不是某种带有置换属性的群，而是群的元素为置换。 对任意置换，可以找到若干互不重合的轮换组合。我们约定 循环节 表示法为顺序排列的置换 [ a 1 , a 2 , . . . a n ] ( 1 , 2 , 3.. n ) [a_1,a_2, ...a_n](1,2,3..n) [ a 1 ​ , a 2 ​ , ... a n ​ ] ( 1 , 2 , 3.. n ) ( a n a_n a n ​ 为位置n上的元素)即为单次轮换操作。如对于置换(2,1)可等价于(1,2)的单次轮换。 特别的, 如 π=(123)(3)(45)(6)(7) 表示拥有7个元素 [ a 1 , a 2 . . . a 7 ] [a_1, a_2...a_7] [ a 1 ​ , a 2 ​ ... a 7 ​ ] 的集合或者列表中， [ a 1 , a 2 , a 3 ] [a_1,a_2,a_3] [ a 1 ​ , a 2 ​ , a 3 ​ ] 轮换, [ a 3 ] [a_3] [ a 3 ​ ] 不变, [ a 4 , a 5 ] [a_4,a_5] [ a 4 ​ , a 5 ​ ] 轮换, [ a 6 , a 7 ] [a_6,a_7] [ a 6 ​ , a 7 ​ ] 不变。

置换的运算逻辑:

例如对于排列或者列表[A,B,C,D], 取(1,2,3)轮换, 记作 [ A , B , C , D ] ( 1 , 2 , 3 ) = [ B , C , A , D ] [A,B,C,D](1,2,3) = [B,C,A,D] [ A , B , C , D ] ( 1 , 2 , 3 ) = [ B , C , A , D ] 又如 [ A , B , C , D ] ( 1 , 2 , 3 ) ( 3 , 4 ) = [ B , C , A , D ] ( 3 , 4 ) = [ B , C , D , A ] [A,B,C,D](1,2,3)(3,4) = [B,C,A,D](3,4) = [B,C,D,A] [ A , B , C , D ] ( 1 , 2 , 3 ) ( 3 , 4 ) = [ B , C , A , D ] ( 3 , 4 ) = [ B , C , D , A ] 再比如，将正方形绕其中心逆时针旋转90度，可以看成是正方形四个顶点 [ A , B , C , D ] [A,B,C,D] [ A , B , C , D ] 的一个轮换(置换)。

置换类型格式</tr>空操作e轮换/互换(1,2) (2,1) (1,2,3)轮换组合(1,2)(2,1) = e</div>

其中2元的置换为互换，互换是特殊的轮换， 轮换是特殊的置换，置换可以写成若干轮换的组合。由这些操作可知，置换操作满足封闭性和交换律，单位元以及逆元的操作都成立，故置换操作可以构成严格意义上的群概念。

置换奇偶性

置换的奇偶性可以简化为 反向对个数的奇偶性, 即满足x,y位置的元素 x < y , s g n ( x ) > s g n ( y ) x<y, sgn(x)>sgn(y) x < y , s g n ( x ) > s g n ( y )

任意置换可以由一列对换产生：对第一个对换我们将置换的第一个元素放到它恰当的位置，第二个对换放第二个元素，等等。给定一个置换σ，我们可用无数种方式将其写成对换之积。我们要证明所有这样一个分解，要么都有偶数个对换，要么有奇数个对换。 置换等价性维基百科 对于一般置换, 都可以可以写成二元互换的复合, 如本题中 A,B,C->C,A,B: (1,2,3) = (1,3)(2,3) , 逆序对[C,A], [C,B]为2 A,B,C->B,C,A: (1,2,3) = (1,2)(2,3), 逆序对[B,A], [B,A]为2 对于偶置换，置换所指定的一个全排序可以保持不变。

总结过后就可以使用原始的对换序列进行置换分解，并且该置换操作为偶置换即可满足全排序条件，实现如下：

def inversion ( ) : 
 inversions = 0 
 for i in range ( n - 1 ) : 
 for j in range ( i + 1 , n ) : 
 if arr [ i ] > arr [ j ] : 
 inversions += 1 
 return inversions % 2 == 0

原文：blog.csdn.net。 这里是静态副本，平台改了、删了，这一份还在。

← CSDN 全部 5 篇