在维基百科上看到了生成下一个排列的算法(这里)
其实也很好理解,对于一个排列如果没有正序, 说明这就是最大的排列了,如果有正序, 我们考虑最后一个如
a[k]a[k + 1]a[k + 1]...a[n], 这里a[k + 1]到a[n]是倒序,这是以a[k]开头的最大的排列, 它的下一个排列是以最小的比a[k]大的数(设为a[l])开头的最小排列, 就是a[l]开头, 剩下的数正序.
这个算法可以处理有重复的数的情况
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 1000; 6 int A[MAXN], n; //sequence to genarate next_permutation 7 8 void swap(int& a, int& b) { 9 int t = a; 10 a = b; 11 b = t; 12 } 13 14 bool next_permutation(int *A, int n) { 15 int k = n - 1; 16 bool has_next = false; 17 while(k) { 18 if(A[k - 1] < A[k--]) {has_next = true; break;} 19 } 20 if(!has_next) return false; 21 int l = n - 1; 22 while(l > k) { // 这里可以改成二分查找的 23 if(A[l] > A[k]) break; 24 --l; 25 } 26 swap(A[k], A[l]); 27 int m = (n - k) >> 1; 28 for (int i = k + 1; i <= k + m; ++i) { 29 swap(A[i], A[k + n - i]); 30 } 31 return true; 32 } 33 34 int main() { 35 cin >> n; 36 for (int i = 0; i < n; ++i) cin >> A[i]; 37 sort(A, A + n); 38 int cnt = 0; 39 do { 40 ++cnt; 41 cout << A[0]; 42 for (int i = 1; i < n; ++i) cout << " " << A[i]; 43 cout << endl; 44 } while(next_permutation(A, n)); 45 cout << cnt << endl; 46 return 0; 47 }
对比一下我们递归生成排列的时候, 先生成以1开头的排列, 再生成以2开头的排列其实是一个道理
原文：http://www.cnblogs.com/ACSeed/p/4834030.html