问题描述:
对任意一个排列Pi,利用两个数的交换,最少多少次能将该排列变成一个升序排列。例子:
2 3 5 4 1--> 1 3 5 4 2 -->1 3 2 4 5 --> 1 2 3 4 5,最少经过三次交换,得到一个升序列。
算法:置换群和环
{3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列
{1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }比较
找出其中所有的"环"
这里的"环"就是指它们互相交换之后能成为标准序列的最小集合
比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
具体找法很简单 首先确定一个不在已找出"环"中的数字 
例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开始的数字 那么这个环就是{1,3}
第二次从7开始,7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8}
第三个环是{6,4}
这样所有的数字都在环中了
交换的次数=(数字总数-环数)=8-3=5

posted on 2009-08-12 11:37 newstar 阅读(222) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。