C++全排列函数

C++STL中的全排列函数

C++STL中的全排列函数为两个：next_permutation和prev_permutation
其中：next_permutation实现升序，而prev_permutation实现降序

下面以123的全排列为例：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int main() { int s[3]={1,2,3}; /**下面为next_permutation的用法*/ do { printf("%d %d %d\n",s[0],s[1],s[2]); } while(next_permutation(s,s+3)); /**下面为prev_permutation的用法*/ /*do { printf("%d %d %d\n",s[0],s[1],s[2]); } while(prev_permutation(s,s+3));*/ return 0; }

当然这只是原始定义的用法，我们可以自定义函数实现我们所需要的顺序

下面有两道例题：

第一题：

G - Ignatius and the Princess II

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, “I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too.” Ignatius says confidently, “OK, at last, I will save the Princess.”

“Now I will show you the first problem.” feng5166 says, “Given a sequence of number 1 to N, we define that 1,2,3…N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it’s easy to see the second smallest sequence is 1,2,3…N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It’s easy, isn’t is? Hahahahaha…”
Can you help Ignatius to solve this problem?

Input

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub’s demand. The input is terminated by the end of file.

Output

For each test case, you only have to output the sequence satisfied the BEelzebub’s demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

Sample Input

6 4
11 8

Sample Output

1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10

题解：这道题看懂题目后就知道只需要进行全排列，输出第m小的序列即可
这道题只需要用到原始定义的升序排列即可
注意小陷阱：" do not output any spaces after the last number. "
AC代码如下：

#include<cstdio> //别用万能头文件#include<bits/stdc++.h>，交了你就知道了，哈哈哈 #include<algorithm> #include<iostream> using namespace std; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int a[1005]; for(int i=0;i<n;i++) a[i]=i+1; int num=0; do { num++; if(num==m) { int flag=0; for(int i=0;i<n;i++) { if(flag==0) { printf("%d",a[i]); flag=1; } else printf(" %d",a[i]); } printf("\n"); break; } } while(next_permutation(a,a+n)); } return 0; }

第二题：

Anagram（POJ 1256）

Description

You are to write a program that has to generate all possible words from a given set of letters.
Example: Given the word “abc”, your program should - by exploring all different combination of the three letters - output the words “abc”, “acb”, “bac”, “bca”, “cab” and “cba”.
In the word taken from the input file, some letters may appear more than once. For a given word, your program should not produce the same word more than once, and the words should be output in alphabetically ascending order.

Input

The input consists of several words. The first line contains a number giving the number of words to follow. Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z. Uppercase and lowercase letters are to be considered different. The length of each word is less than 13.

Output

For each word in the input, the output should contain all different words that can be generated with the letters of the given word. The words generated from the same input word should be output in alphabetically ascending order. An upper case letter goes before the corresponding lower case letter.

Sample Input

3
aAb
abc
acba

Sample Output

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

Hint

An upper case letter goes before the corresponding lower case letter.
So the right order of letters is ‘A’<‘a’<‘B’<‘b’<…<‘Z’<‘z’.

题解：这题就要用到自定义的函数实现字母大写排在小写前面的功能

代码如下：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int cmp(char a,char b) //自定义函数 { if(tolower(a)!=tolower(b)) //tolower是将大写转化为小写 return tolower(a)<tolower(b); else return a<b; } int main() { int n; scanf("%d",&n); char s[20]; while(n--) { scanf("%s",s); int len=strlen(s); sort(s,s+len,cmp); do { printf("%s\n",s); } while(next_permutation(s,s+len,cmp)); //自定义函数的使用 } return 0; }