题目链接:
题意:
问n的全排列中多有少个至少需要交换k次才能变成{1,2,3……n}。
题解:
1.根据过程的互逆性,可直接求{1,2,3……n}至少需要交换多少次才能变成{a1,a2,a3……an},因此可直接把{a1,a2,a3……an}看成是{1,2,3……n}的置换。为什么呢?
答:1 2 3
2 3 1 可知把“2 3 1”看作是经过置换后的序列,则:2-->1(2放到1)、3-->2(3放到2)、1-->3(1放到3)。
把“2 3 1”看作是置换, 则:1-->2(1放到2)、2-->3(2放到3)、3-->1(3放到1)。
所以把序列看成是置换的话,那么它与变成自己的置换的形状完全相同,只是所有箭头的方向都发生了改变。
2.将一个置换分解成若干个循环,对于一个长度为len的循环,需要交换len-1次才能使得里面的每一个元素回到自己的位置(每一次交换都能使得一个元素回到原来的位置,一直交换到最后一个,就直接在自己的位置上。所以位len-1)。
3.根据第二点,即有多少个循环,就能减少多少次交换。而交换了k次,即减少了n-k交换,因此也就有n-k个循环。把n个有区别的元素排列成n-k个循环(圈),即为第一类斯特林数。
代码如下:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include