c++全排列 next_permutation（）函数

c++全排列

转载博客：https://www.cnblogs.com/cstdio1/p/11311500.html

对于next_permutation函数，其函数原型为：
#include < algorithm>
bool next_permutation(iterator start,iterator end)
当当前序列不存在下一个排列时，函数返回false，否则返回true

同时，相对应的，上一个排列即为prev_permutation(int *begin, int end)
看如下代码：

#include <iostream>  
#include <algorithm>  
using namespace std;  
int main()  
{  int num[3]={1,2,3};  do  {  cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;  }while(next_permutation(num,num+3));  return 0;  
}

注意：当我们把while(next_permutation(num,num+3))中的3改为2时，输出就变为了下图所示：

说明此时只针对1，2进行了全排列，有两个，后面的3没有变化，同时改变了数组前两个的值。

由此可以看出，next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

另外，需要强调的是，next_permutation（）在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。

比如，如果数组num初始化为3,1,2，那么输出就变为了：

维基百科上全排列的实现：

循环法：

​
#include <iostream>
using namespace std;
bool arrsame(int* arr, int len, int num) {int i;for (i = 0; i < len; i++)if (arr[i] == num)break;return i != len;
}
bool next_perm(int* perm, const int k, const int n) {int i = k - 1;doperm[i]++;while (arrsame(perm, i, perm[i]) || (perm[i] >= n && i--));if (perm[0] >= n)return 0;for (int num = 0, seat = i + 1; seat < k; num++)if (!arrsame(perm, i + 1, num))perm[seat++] = num;return 1;
}
int main() {int n, k;cout << "perm(n,k):" << endl;cin >> n >> k;if (n < k || k <= 0)return 0;int* perm = new int[k];for (int i = 0; i < k; i++)perm[i] = i;dofor (int i = 0; i < k; cout << ((++i < k) ? ',' : '\\n'))cout << perm[i] + 1;while (next_perm(perm, k, n));delete[] perm;return 0;
}​

递归法：

#include <bits/stdc++.h>
using namespace std;struct prem {int len;vector<int> used, position;function<void(vector<int>&)> action;prem(int l = 0, function<void(vector<int>&)> a = [](vector<int>& position) {}) : len(l), used(l, -1), position(l), action(a) {}void run(int now = -1) {if (now == len - 1) {action(position);return;}int next = now + 1;for (int i = 0; i < len; i++) {if (used[i] == -1) {used[i] = next;position[next] = i;run(next);used[i] = -1;}}}
};
int main() {ios::sync_with_stdio(false), cin.tie(0);int len = 4;prem p(len, [&](vector<int>& p) {for (int i = 0; i < len; i++) {cout << p[i] << " ";}cout << endl;});p.run();return 0;
}

next_permutation 可以自定义比较函数 例如：POJ 1256
题目中要求的字典序是：A’<‘a’<‘B’<‘b’<…<‘Z’<‘z’，所以在用函数之前必须得按照题目要求的进行排序

#include<iostream> //poj 1256 Anagram
#include<string.h>
#include<algorithm>
using namespace std;
int cmp(char a,char b) {if(tolower(a)!=tolower(b))//tolower 是将大写字母转化为小写字母.return tolower(a)<tolower(b);elsereturn a<b;
}
int main() {char ch[20];int n;cin>>n;while(n--) {scanf("%s",ch);sort(ch,ch+strlen(ch),cmp);do {printf("%s\\n",ch);} while(next_permutation(ch,ch+strlen(ch),cmp));}return 0;
}