排列统计

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file findpermutations.in Output file findpermutations.out

【题目描述】

排序是生活中最常见的操作之一,计算机科学对此大有用武之地。稍有常识的人都知道,基于交换的排序时间复杂度下界是O(nlogn)。这意味着可能设计出的最好排序算法将用至少O(nlog(n))次交换操作来给n个整数排序。虽然如此,对给定的n个整数,如果你知道每个数在排序后的位置,那么你总能找到一个包含至多n-1次交换的操作序列来将它们按升序排列。考虑四个元素<1 2 3 4>,有24种可能的排列,并且你知道每个元素在排序后的位置。

如果排列是<2 1 4 3>,至少需要进行2次交换来让它有序(分别交换1,2和4,3)。如果排列是<2 3 4 1>,就至少需要进行3次交换。<4 2 3 1>需要1次交换,<1 2 3 4>不需要交换。用这种方法,我们可以找到包含N个不同整数,并且至少交换K次才能排序的排列数。

【输入格式】

输入包含最多250组数据。

每组数据占1行,含2个正整数N(1<=N<=21)和K(0<=K<N)。

输入结束标志为N=K=0.

【输出格式】

对于每组数据,输出至少交换K次才能排序的排列数。

【样例输入】

3 1
3 0
3 2
0 0

【样例输出】

3
1
2

【来源】

UVa11077 Find the Permutations

刘汝佳,《算法竞赛入门经典训练指南》表2-10

Problemsetter: Md. Kamruzzaman

Special Thanks: Abdullah-al-Mahmud