排列(Permutation or Arrangement)指的是对于已知的一个序列\(\left\{a_n\right\}\)，假定序列\(\left\{a_n\right\}\) 中无重复元素，即\(1 \leq i, j \leq n\wedge i \neq j \rightarrow a_i \neq a_j,\)，从序列的\(n\)个元素中任取\(m (m \leq n)\)个元素，并按照一定的顺序(例如取元素的先后顺序)排列起来所得到的所有结果。当\(m<n\)时，其所有的排列情况称作从序列\(\left\{a_n\right\}\)的\(n\)个不同元素中取出\(m\)个元素的排列，所有排列的个数为\(A^m_n=\frac{n!}{(n-m)!}\)；当\(m=n\)时，其所有的排列情况叫做全排列(Full Permutation)，所有排列的个数为\(A^n_n=n!\)。
全排列算法实现有递归(和非递归两种，递归和非递归实现方式这里分别记录若干种方法。
递归实现全排列算法
1. 交换法
通过全排列排序数的计算式可以得到一个递推式：
\(A^n_n=n \cdot A^{n-1}_{n-1}\)
此式表明，序列\(\left\{a_n\right\}\)的全排列，等价于将\(\left\{a_n\right\}\)中的所有元素依次固定在序列中的同一个位置(一般为首位)，然后对剩余的\(n-1\)个元素进行全排列。直到进行到对长度为2的序列进行全排列，此时仅需要进行一次相邻元素互换即可。之后序列中只剩下一个元素未进行全排列，不再需要交换元素，这时便得到了一个排列结果。
例如，对于序列\(\left\{a_3\right\}=\left\{1,2,3\right\}\)，先将首位元素与序列中的所有元素的位置互换，得到\(3\)个排列：
\(1, 2, 3\) 交换1 1
\(2, 1, 3\) 交换1 2
\(3, 2, 1\) 交换1 3
此时上面\(3\)个序列的首项已经确定，对上面的\(3\)个序列的剩余\(2\)个元素进行全排列，即：
\(1, 2, 3\) 交换2 2
\(1, 3, 2\) 交换2 3
\(2, 1, 3\) 交换1 1
\(2, 3, 1\) 交换1 3
\(3, 2, 1\) 交换2 2
\(3, 1, 2\) 交换2 1
此时上面的所有序列都只剩下最后一个元素未进行排列，无需再交换元素，那么上面得到的所有排列即为\(\left\{a_3\right\}=\left\{1,2,3\right\}\)的全排列。
具体算法实现为：
- 定义固定位的索引为\(k=0\)；
- 对所有的\(k \leq i \leq n\)交换序列\(\left\{a_n\right\}\)中两个元素\(a_k\)和\(a_i\)；
- 交换之后令\(k=k+1\)，重复步骤2；
- 若\(k=n-1\)，即剩一个元素时，得到一种排列结果。递归结束时应得到\(A^n_n\)种排列结果，即全排列。
C++代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> using namespace std; int n; //序列长度n void swap(int *a, int *b) { //交换元素 *a ^= *b; *b ^= *a; *a ^= *b; } void permutation(int array[], int k) { //递归排列 if(k == n - 1) { for(int i = 0; i < n; i++) { cout << array[i] << ' '; } cout << endl; } else { for(int i = k; i < n; i++) { swap(array[i], array[k]); permutation(array, k + 1); swap(array[i], array[k]); } } } int main() { cin >> n; //输入序列长度n int a[n]; for (int i = 0; i < n; ++i ) { //序列a元素为从1到n的整型数值 a[i] = i + 1; } permutation(a, 0); //k = 0 return 0; } |
代码中默认定义序列\(\left\{a_n\right\}\)中的元素为从1到n的整型数值元素，后续介绍的方法使用的序列同上。序列中元素也可以为字符型等基本数据类型。
注意，即使给定的序列为字典序排列，使用交换法得不到按照字典序排序的全排列。
考虑到当序列长度\(n \geq 2\)时，递归交换法的所有交换次数为\(S=\sum\limits_{i=2}^n \prod\limits_{j=i}^n j\)，展开后多项式的最大次项为\(n^{n-1}\)，因此上面的算法实际的时间复杂度为\(O(n^{n-1})\)，未达到\(n \cdot n!\)的量级。不过，其算法可以进一步改进，减少一些无用的交换(如写入一个条件判断语句防止减少本身的交换)来提高效率，达到最高效率时的时间复杂度为\(O(n \cdot n!)\)
除了原序列和一些临时变量之外，程序在运行过程中会调用大量的递归函数入栈，消耗内存，故交换法的空间复杂度理论上为\(O(n)\)，实际上大于\(O(n)\)。
2. 递归生成树法
递归生成树法是我们在平时手动求全排列时常用的一种方法。通过全排列数的计算式可以得到另一种形式的递推式：
\(A^n_n=\prod\limits_{k=1}^n C^1_k\)
此式表明，求给定序列的一个排列，即在当前的\(n\)个元素中抽取一个压入在一个新维护的栈中，然后在剩余的\(n-1\)个元素中抽取一个再压入栈中，直至将序列中剩余的最后一个元素压入栈中，即得到一个排列结果。要求全排列，可将每一次抽取元素的操作写成循环，在抽取结束后将栈中该元素出栈，并将该元素插入回序列原来的位置上，那么最终所有得到的排列结果即为全排列。
对于任意序列\(\left\{a_n\right\}\)都可以作出其全排列的递归生成树，对序列元素进行循环顺序抽取、压栈、出栈、插回的过程，就是对全排列递归生成树的前序遍历过程。
例如对于序列\(\left\{a_3\right\}=\left\{1,2,3\right\}\)，可以作出递归生成树如下图，当从树的第一层(树的根节点\(S\)不在遍历范围内)开始向下遍历，每到树的一个叶子节点时，便能够得到一种排序结果：
vector是实现了stack上操作的线性顺序表，其不仅可以根据数值索引index访问相应位置的元素、实现线性表中的erase和insert操作，也可以进行push和pop的操作。利用vector的上述特性，可以实现上述的算法操作。具体算法实现为：
- 定义vector res作为栈，定义vector a作为顺序表实现序列\(\left\{a_n\right\}\)并初始化；
- 循环对a的每一个元素进行erase操作，并将该元素push入栈res中，对a递归进行该操作，然后将该元素从pop出栈res，并insert回a的原来位置；
- 如果a的长度a.size为0，那么此时栈res中的元素组成的排列即为一种排列结果。递归结束时应得到\(A^n_n\)种排列结果，即全排列。
C++代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<iostream> #include<vector> using namespace std; vector<int> res; //栈res vector<int> a; //序列a int n; //序列长度n void permutation(int k) { if(k == 0) { for (int i = 0; i < n; ++i) { cout << res[i] << ' '; } cout << endl; } else { for (int i = 0; i < k; ++i) { res.push_back(a[i]); //元素入栈 a.erase(a.begin() + i); //抽取元素 permutation(k - 1); a.insert(a.begin() + i, res[n - k]); //插回元素 res.pop_back(); //元素出栈 } } } int main() { cin >> n; //输入序列长度 for (int i = 0; i < n; ++i) { //序列a元素为从1到n的整型数值 a.push_back(i + 1); } permutation(n); return 0; } |
递归树法的一次取元素、入栈、出栈、插入元素的操作的时间复杂度为\(O(c) (c\)为常数\()\)，那么进行的总操作次数为\(S=\sum\limits_{i=1}^n \prod\limits_{j=1}^n j\)，其操作次数明显大于交换法中交换的次数，而且，由于使用的是顺序表vector，在执行删除元素和插入元素时会导致当前位置之后的所有元素位置变动，时间消耗大大提高，故在实现算法时可以使用链表代替顺序表进行操作来提高效率。
对于一个长度为\(n\)的序列而言，该算法总体时间复杂度为\(O(n^n)\)；
除了原序列和一些临时变量之外，程序在运行过程中会调用大量的递归函数入栈，消耗内存，故递归生成树法的空间复杂度理论上为\(O(n)\)，实际上大于\(O(n)\)。
非递归实现全排列算法
3. 蛮力穷举法
穷举法的思路与生成树法的思路一致，都是逐步从序列中抽取元素，在最后一个循环中判断所抽取的元素是否出现重复，如果元素各不相同，则可以确定最终的一个排列结果。
穷举法与其它方法相比，其最大的局限性是需要根据已知序列直接修改代码的循环嵌套成熟来实现求解全排列，因此该方法写出的程序代码不具有普适性。一种代码只能针对其中一种长度的任意序列进行求解全排列。
例如，对于序列长度为5的序列，可以写出如下C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<iostream> using namespace std; int n = 5; //序列长度n=5 int main() { int a[n]; //序列a for (int i = 0; i < n; ++i) { //序列a元素为从1到n的整型数值 a[i] = i + 1; } for (int i1 = 0; i1 < n; ++i1) { //第一层循环 for (int i2 = 0; i2 < n; ++i2) { //第二层循环 if (a[i1] != a[i2]) { for(int i3 = 0; i3 < n; ++i3) { //第三层循环 if (a[i1] != a[i3] && a[i2] != a[i3]) { for (int i4 = 0; i4 < n; ++i4) { //第四层循环 if (a[i1] != a[i4] && a[i2] != a[i4] && a[i3] != a[i4]) { for (int i5 = 0; i5 < n; ++i5) { //第五层循环 if (a[i1] != a[i5] && a[i2] != a[i5] && a[i3] != a[i5] && a[i4] != a[i5]) { cout << a[i1] << ' ' << a[i2] << ' ' << a[i3] << ' ' << a[i4] << ' ' << a[i5] << endl; break; } } } } } } } } } return 0; } |
如果输入的序列为元素非重复的字典序序列，那么得到的全排列结果也按照字典序排列。
对于一个长度为\(n\)的序列而言，其算法包含的\(n\)个嵌套循环，每层循环的时间复杂度\(O(n)\)，总体时间复杂度为\(O(n^n)\)；
除了原序列和一些临时变量之外，未申请任何更多的内存来存储其它变量，故穷举法的空间复杂度为\(O(n)\)。
4. 字典序排列算法
对于序列\(\left\{a_n\right\}\)的全排列，必然存在一种排列顺序将此\(A^n_n\)种排列结果按一定顺序排列起来，从而形成一个新的排列序列\(\left\{P_{A^n_n}\right\}\)。对字符型元素而言，最常见的排列顺序为字典序；对数值型元素而言，最常见的排列顺序为增序。对于使用ASCII码等来表示字符型的语言而言，字符型的字典序排序与数值型增序排序相同，统称为字典序。
在确定排列顺序为字典序之后，对于给定的序列\(\left\{a_n\right\}\)，必然有唯一的一种字典序排列序列\(\left\{P_{A^n_n}\right\}\)与之对应，该排列序列满足下列特征：
- 首项\(P_1\)为原序列\(\left\{a_n\right\}\)的字典序排列；
- 末项\(P_{A^n_n}\)为原序列\(\left\{a_n\right\}\)的反字典序排列；
- 中间项\(P_k (1<k \leq A^n_n)\)为前一项\(P_{k-1}\)的按照字典序得到的下一个排列(可根据算法得到)。
例如对于序列\(\left\{a_6\right\}=\left\{A,B,C,D,E,F\right\}\)，其字典序的排列序列\(\left\{P_{A^6_6}\right\}\)的首项为按字典序排列的原序列
\(P_1=\left\{A,B,C,D,E,F\right\}\)
\(P_2=\left\{A,B,C,D,F,E\right\}\)
\(P_3=\left\{A,B,C,E,D,F\right\}\)
……
\(P_{A^6_6-1}=\left\{F,E,D,C,A,B\right\}\)
\(P_{A^6_6}=\left\{F,E,D,C,B,A\right\}\)
C++的STL<algorithm>头文件中提供了求字典序排列序列的前项和后项的函数prev_permutation和next_permutation，循环调用这两个函数可以得到任意非重复元素序列的全排列。使用上述两个函数求序列的全排列，有三种实现方式：
- 将原序列进行字典序排序，调用next_permutation函数循环求下一个排列，直到求得的序列为反字典序排序的序列为止；
- 将原序列进行反字典序排序，调用prev_permutation函数循环求上一个排列，直到求得的序列为字典序排序的序列为止；
- 保持原序列不变，循环调用next_permutation求下一个排列直到求得的序列为反字典序排序的序列为止，然后再对原序列循环调用prev_permutation求上一个排列直到求得的序列为字典序排序的序列为止。
这里给出C++的STL<algorithm>头文件中next_permutation和prev_permutation函数的用法：next_permutation和prev_permutation的函数参数为两个C++ string类型的字符串迭代器成员变量，如果要对整个字符串求下一个(或上一个)排列，则直接传入字符串迭代器成员变量的首项begin()和末项end()。字符串内的字符根据其ASCII码值来确定大小。函数的返回值为bool型变量，如果传入的字符串存在下一个排列，则返回true，如果不存在，则返回false。具体使用next_permutation和prev_permutation函数求解全排列的代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> #include<algorithm> #include<string> using namespace std; void print(string s) { //输出字符串排列 for (int i = 0; i < s.size(); ++i) { cout << s[i] << ' '; } cout << endl; } void LFP(string str) { //字典序全排列 sort(str.begin(), str.end()); //对序列进行从小到大排列 do { print(str); //输出排列 } while (next_permutation(str.begin(), str.end())); //求下一个字典序排列 } void RLFP(string str) { //反字典序全排列 sort(str.begin(), str.end()); //对序列进行从小到大排列 reverse(str.begin(), str.end()); //序列反向 do { print(str); //输出排列 } while (prev_permutation(str.begin(), str.end())); } int main() { string str; cin >> str; //输入任意序列 LFP(str); //字典序全排列 RLFP(str); //反字典序全排列 return 0; } |
注：LFP是Lexicographical Full Permutation(字典序全排列)的缩写；RLFP是Reverse Lexicographical Full Permutation(反字典序全排列)的缩写。
通常情况下给定的原序列\(\left\{a_n\right\}\)为字典序排序的序列，故常用的实现方法为前两种方法，如果给定的原序列非字典序排序的序列，可以使用排序算法来对原序列进行排序操作。
next_permutation函数的具体算法为：
- 对于全排列序列的某一项\(P_m (1 \leq m \leq A^n_n-1)\)，找到特定的相邻元素\(a_k, a_{k+1} (1 \leq k \leq n-1)\)，其中\(k\)为满足\(a_i \leq a_{i+1} (1\leq i \leq n-1)\)中\(i\)的最大值。即从右向左遍历序列\(\left\{a_n\right\}\)，找到第一个满足逆序的相邻元素对\(a_k,a_{k+1}\)；
- 对于序列\(\left\{a_k,…,a_n\right\}\)，找到特定的元素\(a_j\)，其中\(j\)为满足\(a_k \leq a_i (k+1 \leq i \leq n)\)中\(i\)的最大值，即从右向左遍历序列\(\left\{a_k,…,a_n\right\}\)，找到第一个满足\(a_k \leq a_j\)的元素\(a_j\)；
- 逆序变换序列\(\left\{a_{k+1},…,a_n\right\}\)，此时即得到序列\(a_n\)的下一个字典序排列项\(P_{m+1}\)；
- 对新得到的全排列序列项重复步骤1、2、3，直到得到\(P_{A^n_n}\)为止。
prev_permutation函数的具体算法与next_permutation类似。permutation函数的具体算法为：
- 对于全排列序列的某一项\(P_m (2 \leq m \leq A^n_n)\)，找到特定的相邻元素\(a_k, a_{k+1} (1 \leq k \leq n-1)\)，其中\(k\)为满足\(a_i \geq a_{i+1} (1\leq i \leq n-1)\)中\(i\)的最大值。即从右向左遍历序列\(\left\{a_n\right\}\)，找到第一个满足正序的相邻元素对\(a_k,a_{k+1}\)；
- 对于序列\(\left\{a_k,…,a_n\right\}\)，找到特定的元素\(a_j\)，其中\(j\)为满足\(a_k \geq a_i (k+1 \leq i \leq n)\)中\(i\)的最大值，即从右向左遍历序列\(\left\{a_k,…,a_n\right\}\)，找到第一个满足\(a_k \geq a_j\)的元素\(a_j\)；
- 逆序变换序列\(\left\{a_{k+1},…,a_n\right\}\)，此时即得到序列\(a_n\)的上一个字典序排列项\(P_{m-1}\)；
- 对新得到的全排列序列项重复步骤1、2、3，直到得到\(P_1\)为止。
在上述两个算法的前两个步骤中，为了保证在序列中有重复元素的情况下也可以正确求出下一个(或上一个)排列，在判断大小时考虑到等于的情况；如果序列中没有重复元素，那么可以忽略等于的情况，只考虑大于或小于的情况。
C++代码实现：
注：这里仅给出next_permutation算法的实现，prev_permutation算法仅需在next_permutation算法中改变两个不等号的方向，其余部分相同，需要更改的位置在下面代码中已用注释标出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<iostream> using namespace std; void swap(int *a, int *b) { //元素交换 *a ^= *b; *b ^= *a; *a ^= *b; } int main() { int n; //序列长度n cin >> n; int a[n]; //序列a for (int i = 0; i < n; ++i) { //序列a元素为从1到n的整型数值 a[i] = i + 1; } while (true) { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } cout << endl; int k = n - 2; //k ak<ak+1 int j = n - 1; //j ak<aj for ( ; k >= 0 && a[k] >= a[k + 1]; --k ) {} //找到k, prev_permutation将a[k] >= a[k + 1]改为a[k] <= a[k + 1] if (k == -1) { //得到反字典序序列退出循环 break; } for ( ; j > k && a[k] >= a[j]; --j ) {} //找到j, prev_permutation将a[k] >= a[j]改为a[k] <= a[j] swap(a[j], a[k]); //交换a[k]和a[j] for (int i = 0; i < (n - 1 - k) / 2; ++i) { //逆序a[k]之后的序列 swap(a[k + 1 + i], a[n - 1 - i]); } } return 0; } |
prev_permutation算法的时间复杂度为\(O(n)\)，故字典序排列法的时间复杂度为\(O(n \cdot n!)\)；
除了原序列和一些临时变量之外，未申请任何更多的内存来存储其它变量，故字典序法空间复杂度为\(O(n)\)。
5. Steinhaus-Johnson-Troffer算法
Steinhaus-Johnson-Troffer算法(以下简称SJT算法)是一种基于最小变换的全排列生成算法。在该算法中，通过相邻元素的交换(而非任意两元素交换)来依次得到下一个不重复的排列。每一次循环操作都会进行一次满足特定条件的元素互换，当形成的排列不能满足特定条件时，则循环终止，操作中所得到的全部排列结果即为原序列的全排列。
SJT算法生成全排列的具体算法如下：
- 设定原序列\(\left\{a_n\right\}\)为字典序最小排列，并且为序列中的每一个元素都设定一个移动方向，初始移动方向均为向左；
- 如果序列中一个元素的移动方向存在相邻元素(不能越界)且相邻元素的值比该元素的值小(或排在字典序之前)，则认定该元素可以进行一次合法移动，在序列中找到能够进行合法移动的最大元素；
- 将该最大的合法移动元素与其移动方向的相邻元素交换位置；
- 对于序列中比最大的合法移动元素的值更大(或排在字典序之后)的元素，反转其移动方向；
- 重复步骤2、3、4，直到序列中不存在能够进行合法移动的元素为止。
C++代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> using namespace std; void swap(int &a, int &b) { //元素交换 a ^= b; b ^= a; a ^= b; } void print(int a[], int n) { //序列输出 for (int i = 0; i < n; ++i) { cout << a[i] << ' '; } cout << endl; } int main() { int n; //序列长度n cin >> n; int a[n], d[n]; //序列a，方向序列d for (int i = 0; i < n; ++i) { a[i] = i + 1; //序列a元素为从1到n的整型数值 d[i] = -1; //序列d元素为-1(方向向左)和1(方向向右) } bool flag = true; //序列中存在合法移动的状态标志 while (flag) { flag = false; print(a, n); int max = 0; //最大合法移动元素，初值为0 int max_index = 0; //最大合法移动元素下标，初值为0 for (int i = 0; i < n; ++i) { //在序列中寻找合法移动的最大元素 if ((d[i] < 0 && i > 0 && a[i] > a[i - 1]) //方向向左，不超过左边界，且比相邻元素大 || (d[i] > 0 && i < n - 1 && a[i] > a[i + 1])) { //方向向右，不超过右边界，且比相邻元素大 if (a[i] > max) { max = a[i]; max_index = i; flag = true; //状态有效 } } } swap(a[max_index], a[max_index + d[max_index]]); //交换a序列元素值 swap(d[max_index], d[max_index + d[max_index]]); //交换d序列元素方向 for (int i = 0; i < n; ++i) { if (a[i] > max) { d[i] = -d[i]; //所有比合法移动最大元素大的元素的方向反转 } } } return 0; } |
注意，给定的初始序列为字典序排列，但使用SJT算法依次交换元素不能得到按照字典序排序的全排列。
在该算法中，一次元素交换操作的时间复杂度为\(O(n)\)，故Steinhaus-Johnson-Troffer算法的时间复杂度为\(O(n \cdot n!)\)；
除了原序列、方向序列和一些临时变量之外，未申请任何更多的内存来存储其它变量，故Steinhaus-Johnson-Troffer算法的空间复杂度为\(O(n)\)；
全排列算法的应用
全排列算法作为穷举法，如果要求得所有排列，那么算法的时间复杂度至少为\(O(n \cdot n!)\)，因此全排列算法只适用于一些规模较小的排列和填数问题。像时间限制为1000ms的题目，对于时间复杂度为\(O(n!)\)的算法，最大的数据范围为\(n=11\)，如果提前适当排出一些无关项，可以将最大数据范围扩大到\(n=12\)甚至\(n=13\)。在题目规模较小\((n \leq 11)\)时，整个全排列算法可以不作修改直接使用，只需在每一次得到一个排列结果的位置，加一些条件判断语句来判断当前填写结果是否符合题目要求即可；如果规模较大\((n=12\)或\(n=13)\)，则需要在开始全排列之前手动去除掉一部分不符合要求的结果，以防程序运行超时；或者选用更为适合题目的其它算法。
这里举一个全排列算法解决问题的例子，其它相似的问题均可举一反三：
填数问题
出自：2016年第七届蓝桥杯大赛个人赛省赛(软件类)C语言A组第3题
如下的十个格子：
填入0~9十个数字，要求：连续的两个数字不能相邻(左右、上下、对角都算相邻)。
一共有多少种可能的填数方案？
本题实际上考察的是无向图的DFS算法。但是由于本题满足规模较小且填入数字不重复的特点，所以也可以使用全排列算法求解，这里使用的是字典序法求解全排列，在条件判断语句中需要考虑到所有相邻格子的情况，如果所有相邻格子两数之差的绝对值大于1，则算作一种有效填数方案。
C++代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<iostream> #define n 10 #define abs(a) ((a) > 0 ? (a) : -(a)) //返回整型绝对值 using namespace std; void swap(int *a, int *b) { //两数交换 *a ^= *b; *b ^= *a; *a ^= *b; } int main() { int* a = new int[n]; for (int i = 0; i < n; a[i] = i++ ) {} //数组初始化为0-9 int count = 0; while (true) { //全排列 if ( abs(a[0] - a[1]) != 1 && abs(a[1] - a[2]) != 1 //横向第1行 && abs(a[3] - a[4]) != 1 && abs(a[4] - a[5]) != 1 && abs(a[5] - a[6]) != 1 //横向第2行 && abs(a[7] - a[8]) != 1 && abs(a[8] - a[9]) != 1 //横向第3行 && abs(a[0] - a[4]) != 1 && abs(a[1] - a[5]) != 1 && abs(a[2] - a[6]) != 1 //纵向第1行-第2行 && abs(a[3] - a[7]) != 1 && abs(a[4] - a[8]) != 1 && abs(a[5] - a[9]) != 1 //纵向第2行-第3行 && abs(a[0] - a[5]) != 1 && abs(a[1] - a[6]) != 1 //右斜向第1行-第2行 && abs(a[3] - a[8]) != 1 && abs(a[4] - a[9]) != 1 //右斜向第2行-第3行 && abs(a[0] - a[3]) != 1 && abs(a[1] - a[4]) != 1 && abs(a[2] - a[5]) != 1 //左斜向第1行-第2行 && abs(a[4] - a[7]) != 1 && abs(a[5] - a[8]) != 1 && abs(a[6] - a[9]) != 1 //左斜向第1行-第2行 ) { count++; } int k = n - 2, j = n - 1; for ( ; k >= 0 && a[k] > a[k + 1]; --k ) {} if (k == -1) { break; } for ( ; j > k && a[k] > a[j]; --j ) {} swap(&a[j], &a[k]); for (int i = 0; i < (n - 1 - k) / 2; ++i) { swap(&a[k + 1 + i], &a[n - 1 - i]); } } cout << count << endl; return 0; } |
本题答案为1580。
后记
全排列算法属于排列算法中的特例。在一般的求排列的算法中，要求得所有排列，需要先求得已知序列\(\left\{a_n\right\}\)的所有组合，然后对所有组合求全排列，最后得到的结果为排列的结果。求已知序列的所有组合的算法与求全排列的算法相似但略有不同。在下一篇文章将重点讲述全组合算法(Full Combination)。
感谢阅读。如对本文内容有意见和建议，欢迎通过首页的联系方式联系作者，或在文章下方进行评论。
本文采用CC BY-NC-SA 4.0 国际许可协议进行许可。转载请注明出处：https://www.scxs-studio.com/?p=485。
Joseph
zwdong