全排列算法

递归

---

不断与当前索引处元素交换，进入递归。

---

字典序

---

从尾端寻找第一个变小的数i，再从尾端寻找比他大于或等于最小数j，交换，将索引i后面数逆转。

---

#include <iostream> #include <vector> using namespace std; //宏定义后面不要加‘;’或其他符号，会一致被替换除了连续符号‘\’ #define N 4 //permutation：递归写法 //parameter:res结果，A结果数，n序列大小，m结果索引，beg当前序列索引 void createPermutation(vector<vector<int>> &res, int &A, int &n, int &m,int beg) { if (m < A) { vector<int> v = res[m-1]; for (int i = beg+1;i <=n;++i) { createPermutation(res, A, n, m, beg + 1); if (i == n) break; //因为跟末尾元素交换后++i就==n了，还没有进入递归，所以改了范围 vector<int> v1{ v }; swap(v1[beg], v1[i]); res[m++] = v1; } } } //字典序 //parameter：beg起始，end结束 bool nextPermutation(vector<int>::iterator beg, vector<int>::iterator end) { //3 4 6 9 8 7 5 2 1 if (beg == end) return false;//空 auto itI = beg; if ((++itI) == end) return false;//一个元素 auto itJ = end; --itJ; itI = itJ; --itI; for (;;--itI,--itJ) { if (*itI < *itJ)//存在下一个排列 { auto itK = end; while (*itI >= *(--itK));//寻找不比他小的 iter_swap(itI, itK);//迭代器交换 reverse(itJ, end);//恢复升序 return true; } if (itI == beg) { reverse(beg, end); return false; } } } int main() { vector<int> pos(N); for (int i = 0;i < N;++i) { pos[i] = i; } pos[3] = 1; //create int n = N, A = 1; while (n != 1) { A *= n; --n; } n = 1; cout << "字典序" << endl; do { cout << n << ":\t"; for (const int &im : pos) { cout << im << "\t"; } cout << endl; ++n; } while (nextPermutation(pos.begin(), pos.end())); //next_permutation(beg,end); cout << "递归" << endl; n = 1; vector<vector<int>> res(A); int m = 0; res[m++] = pos; n = N; createPermutation(res, A, n, m, 0); cout << N << "\t全排列\t" <<A<< endl; n = 1; for (const auto &vm : res) { cout << n << ":\t"; for (const auto &im : vm) { cout << im << "\t"; } cout << endl; ++n; } cout << "\t\t\t@zem" << endl; system("pause"); return 0; }

---