全排列next_permutation的用法（稍微有点改动）

/* 分析next_permutation函数执行过程: 假设数列 d1,d2,d3,d4…… 范围由[first,last)标记，调用next_permutation使数列逐次增大，这个递增过程按照字典序。 例如，在字母表中，abcd的下一单词排列为abdc，但是，有一关键点，如何确定这个下一排列为字典序中的next， 而不是next->next->next…… 若当前调用排列到达最大字典序，比如dcba，就返回false，同时重新设置该排列为最小字典序。 返回为true表示生成下一排列成功。下面着重分析此过程： 根据标记从后往前比较相邻两数据，若前者小于（默认为小于）后者，标志前者为X1（位置PX）表示将被替换， 再次重后往前搜索第一个不小于X1的数据，标记为X2。交换X1，X2，然后把[PX+1，last)标记范围置逆。完成。 要点：为什么这样就可以保证得到的为最小递增。 从位置first开始原数列与新数列不同的数据位置是PX，并且新数据为X2。[PX+1，last)总是递减的， [first,PX)没有改变，因为X2>X1,所以不管X2后面怎样排列都比原数列大，反转[PX+1，last）使此子数列(递增)为最小。 从而保证的新数列为原数列的字典序排列next。 */ /* 由于排列与组合之间有着密切的联系，我们很容易就可以从“排列”获得“组合”。 从n个元素中任取r个元素的组合，有n! / (r! * (n-r)!)个。 这些组合可用多重集{r·1, (n-r)·0}的全排列来生成，请看示例程序： */ #include <algorithm> #include <vector> #include <iostream> using namespace std; int main() { // 从n个元素中，任取r个元素的所有组合： // G++[o] BCC5[o] VC7[x] const int n = 7; const int r = 4; // 0 <= r <= n vector<int> p, set; p.insert(p.end(), r, 1); p.insert(p.end(), n - r, 0); for ( int i = 0; i != p.size(); ++i ) set.push_back(i+1); int count = 0; do { for ( int i = 0; i != p.size(); ++i ) if(p[i]) cout << set[i] << " "; count++; cout << "/n"; } while (prev_permutation( p.begin(), p.end() )); cout << "There are " << count << " combinations in total."; } hdu 1027 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int main() { int num[1005]; for(int i = 0; i < 1005; i++) num[i] = i; int n, m; while(cin >> n >> m) { for(int i = 1 ; i < m ; i++) next_permutation(num + 1, num + 1 + n); for(int i = 1; i <= n; i++) { if(i != n) printf("%d ", num[i]); else printf("%d/n", num[i]); } sort(num + 1, num + 1 + n); } } pku 1371 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int cmp(char x, char y) { return x < y; } int main() { char str[1005]; while(scanf("%s", str) != EOF) { int len = strlen(str); sort(str, str + len, cmp); printf("%s/n", str); while(next_permutation(str, str + len)) printf("%s/n", str); } return 0; } pku 3187 #include <iostream> #include <algorithm> #include <cstdio> using namespace std; int main() { int num[15]; int s[15]; int n, sum; while( cin >> n >> sum ) { for(int i = 1; i <= n; i++) num[i] = i; while(1) { for(int i = 1; i <= n; i++) s[i] = num[i]; int m = n; while(m) { for(int i = 1; i < m; i++) s[i] = s[i] + s[i + 1]; m--; } if(sum == s[1]) { for(int i = 1; i <= n; i++) { if(i != n) printf("%d ", num[i]); else printf("%d/n", num[i]); } break; } next_permutation(num + 1, num + 1 + n); } } } pku 1146 #include<stdio.h> //印的继任者如果存在代码或消息`没有后继'如果给定的代码是在该序列中的最后一套字符。 #include<algorithm> using namespace std; int main() { int len; char s[51]; while(scanf("%s",s)!=EOF) { if(s[0]=='#') break; len=strlen(s); if(next_permutation(s,s+len)) printf("%s/n",s); else printf("No Successor/n"); } return 0; } 转自：http://blog.csdn.net/yueashuxia/archive/2010/04/18/5498646.aspx