排列组合例题

1．利用斯特林(Stirling)公式求解n!的位数:

#include

#include

using namespace std;

//const double e=2.7182818284590452354, pi = 3.1415926535793239;

const double e=exp(1),pi=2*asin(1);

int stirling(int n) //返回n阶乘的位数

{

return int(0.5*log10(2*pi*n)+n*log10(n/e))+1;

}

int main()

{

int n;

cin>>n;

cout<return 0;

}

n!的位数为[lg10(n*(n-1)*(n-2)*…..*1)]+1

=[lg10(n)+lg10(n-1)+lg10(n-2) +….+lg10(1)]+1

高德纳的《计算机程序设计艺术》中，

n! = sqrt(2*π*n)*((n/e)^n)*(1+1/(12*n)+1/(288*n*n) + O(1/n^3))

例1：Poj1833

给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。

给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。 比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

输入数据

第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=)，第二行有n个正整数，是1，2 … n的一个排列。

输出要求

对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。

输入样例

3

3 1

2 3 1

3 1

3 2 1

10 2

1 2 3 4 5 6 7 8 9 10

输出样例

3 1 2

1 2 3

1 2 3 4 5 6 7 9 8 10

解题思路：

这道题目，最直观的想法是求出1到n的所有排列，然后将全部排列排序，但是n最大可以是1024，1024! 个排列，几乎永远也算不出来，算出来也没有地方存放。

那么，有没有公式或规律，能够很快由一个排列推算出下k个排列呢？

实际上寻找规律或公式都是徒劳的，只能老老实实由给定排列算出下一个排列，再算出下一个排列，……一直算到第k的排列。鉴于k的值很小，最多只有，因此这种算法应该是可行的。

如何由给定排列求下一个排列？不妨自己动手做一下。比如：

“2 1 4 7 6 3 5”的下一个排列是什么？

容易，显然是“2 1 4 7 6 5 3”

那么，再下一个排列是什么？有点难了，是“2 1 5 3 4 6 7”。

以从“2 1 4 7 6 5 3”求出下一个排列 “2 1 5 3 4 6 7”作为例子，可以总结出求给定排列的下一个排列的步骤：

假设给定排列中的n个数从左到右是a1, a2, a3……an 。

1) 从an开始，往左边找，直到找到某个aj，满足aj-1 < aj（对上例, 这个aj就是 7，aj-1 就是4）。

2) 在 aj 、aj+1…… an 中找到最小的比aj-1 大的数，将这个数和 aj-1 互换位置（对上例, 这个数就是5，和4换完位置后的排列是 “2 1 5 7 6 4 3”）。

3) 将从位置j到位置n的所有数（共n-j+1个）从小到大重新排序，排好序后，新的排列就是所要求的排列。（对上例，就是将“7 6 4 3”排序，排好后的新排列就是“2 1 5 3 4 6 7”）。

参考程序：

1. #include

2. #include

3. #define MAX_NUM 1024

4. int an[MAX_NUM + 10];

5. //用于排序的比较函数

6. int MyCompare( const void * e1, const void * e2)

7. {

8. return * ((int *) e1) - * ((int *) e2);

9. }

10.

11. main()

12. {

13. int M;

14. int n, k, i, j;

15. scanf(\"%d\

16. for (int m = 0; m < M; m ++ ) {

17. scanf(\"%d%d\ &k);

18. //排列存放在 an[1] .... an[n]

19. for( i = 1; i <= n; i ++ )

20. scanf(\"%d\

21. an[0] = 100000; //确保an[0]比排列中所有的数都大

22. for( i = 0; i < k ;i ++ ) { //每次循环都找出下一个排列

23. for( j = n ; j >= 1 && an[j-1] > an[j] ; j -- ) ;

24. if( j >= 1 ) {

25. int nMinLarger = an[j];

26. int nMinIdx = j;

27. //下面找出从an[j]及其后最小的比an[j-1]大的元素及其下标

28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. for( int kk = j; kk <= n; kk ++)

if( nMinLarger > an[kk] && an[kk] > an[j-1]) {

nMinLarger = an[kk];

nMinIdx = kk;

}

//交换位置

an[nMinIdx] = an[j-1];

an[j-1] = nMinLarger;

qsort( an + j, n - j + 1 , sizeof(int), MyCompare);

}

else { //an里的排列已经是降序了，下一个排列就是 1 2 3 。。。 for( j = 1; j <= n; j ++ )

an[j] = j;

n

41. }

42. }

43. for( j = 1; j <= n; j ++ )

44. printf(\"%d \j]);

45. printf(\"\\n\");

46. }

47. }

语句36是对一个数组的局部进行排序。qsort函数并不要求第一个参数必须是一个数组的开始地址，只要是待排序的一片连续空间的开始地址即可。同样，qsort的第二个参数也不必一定是整个数组的元素个数，只要是待排序的元素个数即可。

实现技巧

1．把排列存放在an[1] .... an[n]，而在an[0]存放一个比排列中所有的数都大的数，这个an[0]所起的作用通常称之为“哨兵”。有了“哨兵”，就可以写语句23:

for(j=n;j>=1 && an[j-1]>an[j];j--);

而不必担心j-1小于0导致数组越界。如果没有“哨兵”，那么写到相当于语句23的这个for循环的时候，就要判断j-1小于0的情况，比较罗嗦，也容易出错。放置“哨兵”是在数组或链表中进行各种操作时的常用做法。

2. 用标准模板库中的next_permutation 算法直接就能求给定排列的下一个排列，根本不需动脑筋。

例2.Poj3252

Round Numbers

Time Limit: 2000MS Memory Limit: 65536K

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, Paper, Scissors', 'Ro, Sham, Bo', and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin because it's so hard to toss using hooves.

They have thus resorted to \"round number\" matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both \"round numbers\cow wins,

otherwise the second cow wins.

A positive integer N is said to be a \"round number\" if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many \"round numbers\" are in a given range.

Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

Input

Line 1: Two space-separated integers, respectively Start and Finish.

Output

Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish

Sample Input

2 12

Sample Output

6

题意：找两个数之间有多少个round number。

round number的定义是：把一个数化成2进制，如果0的个数>=1的个数。那么该数为round number。

思路：

计算出从1到finish之间有多少个round number，再算出从1到start-1之间有多少个round number。两者相减即为两者之间的数。

之所以算出从1到start-1，因为如果start本身时一个round number，那么最后结果就会少1。

求区间[0,num]内round numbe的方法：

先把num转化为二进制数，则每个1代表的就是2^n（也就是说num比2^n个数大）；

然后就求出这2^n个数有多少个数为round number。

因为这2^n个数长度都是相等的，容易用排列组合做。

设howmany(n,k)表示n位2进制、有k个0的round number数。一位。那么有递推公式：

howmany(n,k)=howmany(n-1,k-1) (if B[n-1]==0)

howmany(n,k)=C(n-2,k-1)+howmany(n-1,k) (if B[n-1]==1)

#include

using namespace std;

int C[33][33],MAX[33],B[33];

int tobinary(int b)

{

int i=1;

数组记录该数的2进制的每B

while(b)

{

B[i++]=b%2;

b/=2;

}

return i-1;

}

void init()

{

int i,j;

C[1][0]=C[1][1]=1;

for(i=2;i<=32;i++)

{

C[i][0]=1;

for(j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];

}

MAX[1]=0;

for(i=2;i<=32;i++)

for(j=(i+1)/2;j}

int howmany(int n, int k, int *p)

{

if(k>=n || k<0) return 0;

if((n==1 && k==0) || (n==2 && k==1)) return 1;

if(p[n-1]==0) return howmany(n-1,k-1,p);

else return C[n-2][k-1]+howmany(n-1,k,p);

}

int compute(int n)

{

int i, ans=0, len=tobinary(n);

for(i=(len+1)/2; ifor(i=1; ireturn ans;

}

int main()

{

init();

int start, finish;

scanf(\"%d%d\

printf(\"%d\\n\

return 0;

}

例3：poj1019

Number Sequence

Time Limit: 1000MS Memory Limit: 10000K

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.

For example, the first 80 digits of the sequence are as follows:

112123123412345123456123456712345678123456712345671012345671011123456710

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤i≤21474837)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

2

8

3

Sample Output

2

2

#include

#include

using namespace std;

const int max = 32000;

unsigned int a[32000], s[32000];

void prepare()

{

a[1] = 1;

s[1] = 1;

for(int i=2; i<32000; i++)

{

a[i] = a[i-1] + (int)(log10((double)i)) + 1;

s[i] = s[i-1] + a[i];

}

}

int calc(int number)

{

int i, location;

int length = 0;

for(i=1; s[i] < number; i++);//number is in the ith subset

location = number - s[i-1];

for(i=1; location>length; i++)

{

length += (int)(log10((double)i))+1;

}

//length-location is the redudant numbers for the ith number

//for instance: 123, if you want to get 2, length-location would be 1

//use 12 mod 10, the result would be 2

return (i-1) / (int)(pow((double)10, length-location)) % 10;

}

int main()

{

prepare();

int count = 0;

int number = 0;

cin >> count;

for(int i = 0; i{

cin >> number;

cout << calc(number) << endl;

}

return 0;

}

思考题：poj 1850

Time Limit: 1000MS Memory Limit: 30000K

Transmitting and memorizing information is a task that requires different coding systems for the best use of the available space. A well known system is that one where a number is associated to a character sequence. It is considered that the words are made only of small characters of the English alphabet a,b,c, ..., z (26 characters). From all these words we consider only those whose letters are in lexigraphical order (each character is smaller than the next character).

The coding system works like this:

• The words are arranged in the increasing order of their length.

• The words with the same length are arranged in lexicographical order (the order from the dictionary).

• We codify these words by their numbering, starting with a, as follows:

a - 1

b - 2

...

z - 26

ab - 27

...

az - 51

bc - 52

...

vwxyz - 83681

...

Specify for a given word if it can be codified according to this coding system. For the affirmative case specify its code.

Input

The only line contains a word. There are some constraints:

• The word is maximum 10 letters length

• The English alphabet has 26 characters.

Output

The output will contain the code of the given word, or 0 if the word can not be codified.

Sample Input

bf

Sample Output

55

大致题意：（与POJ1496基本一致）

输出某个str字符串在字典中的位置，由于字典是从a=1开始的，因此str的位置值就是在str前面所有字符串的个数+1

规定输入的字符串必须是升序排列。不降序列是非法字符串。

不要求用循环输入若干组字符串，但若输入非法字符串则输出0，且结束程序（！！）

本题Str最长为10个字符

解题思路：

第一步：判断输入的str是否是升序序列。

第二步：计算比str长度少的所有字符串个数。

第三步，就是求长度等于str，但值比str小的字符串个数

第四步，把前面找到的所有字符串的个数之和再+1，就是str的值

之所以+1，是因为此前的所有操作都只是找str之前的字符串，并不包括str本身

#include

#include

using namespace std;

int c[27][27]={0};

void play_table() //打表，利用杨辉三角计算每一个组合数C(n,m)

{

for(int i=0;i<=26;i++)

for(int j=0;j<=i;j++)

if(j==0||i==j) c[i][j]=1;

else c[i][j]=c[i-1][j-1]+c[i-1][j];

c[0][0]=0;

}

int main()

{

play_table();

int i,j;

char str[11];

while(cin>>str)

{

int len=strlen(str);

for(i=1;iif(str[i-1]>=str[i])

{

cout<<0<本题只要求输入一次就允许结束程序

} //这是与POJ1496的最隐蔽区别

int sum=0;

//计算长度比str小的字符串个数

for(i=1;i//计算长度等于len，但值比str小的字符串个数

for(i=0;i{

char ch= (!i)?'a':str[i-1]+1; //ch=str[i-1]+1

while(ch<=str[i]-1)

{

sum+=c['z'-ch][len-1-i];

//小于等于ch的字符不允许再被选择,能够选择的字符总数为'z'-ch

//ch位置后面剩下的位数，就是从'z'-ch选择len-1-i个字符

ch++;

}

}

cout<return 0;

}

包括str本身，因此这里要+1