star

搜索

RSS

RSS Link

计数器

139724

求一个数是第几个排列数

2010年8月06日 00:47 | Comments(81) | Category:C语言 | Tags:

根据康托展开公式:$$C = \left\sum_{i=1}^{n}a_i(i-1)!\right$$

a[i]为第i个数比后面的都小的个数。

#include <stdio.h>
#include <string.h>
int FAC[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int CantorExp(char *s, int n)
{
	int i, j, t, num = 0;
	for(i = 0; i < n; ++i)
	{
		t = 0;
		for(j = i+1; j < n; ++j)
			if(s[j] < s[i])
				++t;
		num += FAC[n-i-1]*t;
	}
	return num+1;
}
int main(int argc, char *argv[])
{
	char s[] = "1324";	//输入一个排列数的字符串序列 
	printf("%d", CantorExp(s, strlen(s)));
	return 0;
}