见紫书 P194
题目描述：
关于书中的最初的分析，其思想是直接暴力列举出给定整数序列的全排列，然后逐个检验其合法性。
实验代码如下：
for (int i = 2; i <= n * 2; i++) isp[i] = is_prime(i); // 生成素数表，加快后续判断
for (int i = 0; i < n; i++) A[i] = i + 1; // 第一个排列
do {
int ok = 1;
for (int i = 0; i < n; i++) if (!isp[A[i] + A[(i + 1) % n]]) { ok = 0; break; } // 判断合法性，因为是环，所以防止最后一个数越界，要对（i+ 1）取模
if (ok) {
for (int i = 0; i < n; i++) printf("%d ", A[i]); // 输出序列
printf("
");
}
} while (next_permutation(A + 1, A + n)); // 1 的位置不变
读到这里，我对于 next_permutation() 这个函数其实是有点疑问的，仔细一想，我们只需要把它看成一个黑盒子就好，每一次它都会从排除了 1 的数组子序列的全排列中取出一个不重复的序列，然后一一验证。
这里我使用 Python 生成全排列验证过，发现生成 10 个数字的全排列，其种数就已经很大了，所以，这个方法并不适合解决这个问题。
书中给出的标准解法是使用回溯的思想，代码如下：
void dfs(int cur) {
if (cur == n && isp[A[0] + A[n - 1]]) { // 递归边界, 别忘了测试第一个数和最后一个数
for (int i = 0; i < n; i++) {
printf("%d ", A[i]); // 打印方案
}
printf("
");
} else {
for (int i = 2; i <= n; i++) { // 尝试放置每个数 i
if (!vis[i] && isp[i + A[cur - 1]]) { // 如果 i 没有用过, 并且与前一个数之和为素数
A[cur] = i;
vis[i] = 1; // 标记已经使用过
dfs(cur + 1);
vis[i] = 0; // 恢复标记
}
}
}
}
全部的测试代码：
#include <iostream>
using namespace std;
int n = 12; // 全局变量, 对应问题中的 n
int isp[40], A[20], vis[20]; // isp 表示是否是素数; 我们在主函数中先把 1 到 39 中的素数给筛选出来, 存入这个数组; vis 用来表示是否被访问过
// 判断是否是素数
int is_prime(int t) {
if (t < 2)
return false;
for (int i = 2; i * i <= t; i++) {
if (t % i == 0)
return false;
}
return true;
}
void dfs(int cur) {
if (cur == n && isp[A[0] + A[n - 1]]) { // 递归边界, 别忘了测试第一个数和最后一个数
for (int i = 0; i < n; i++) {
printf("%d ", A[i]); // 打印方案
}
printf("
");
} else {
for (int i = 2; i <= n; i++) { // 尝试放置每个数 i
if (!vis[i] && isp[i + A[cur - 1]]) { // 如果 i 没有用过, 并且与前一个数之和为素数
A[cur] = i;
vis[i] = 1; // 标记已经使用过
dfs(cur + 1);
vis[i] = 0; // 恢复标记
}
}
}
}
int main() {
// 初始化 isp 数组, 生成素数表, 加快后续判断
for (int i = 0; i <= n * 2; i++) {
isp[i] = is_prime(i);
}
// 初始化 vis 数组
for (int i = 0; i < 20; i++) {
vis[i] = 0;
}
vis[1] = 1; // 1 是确定已经被访问过的
// 初始化 A 数组
for (int i = 1; i < n; i++) {
A[i] = 0;
}
A[0] = 1; // A 数组中的第一个元素是 1, 这是题目给出的条件
dfs(1);
return 0;
}
注意，代码中的全局变量 n 即对应题目中的 n。上面定义了三个数组，要注意它们的使用，其中，isp 的下标即代表数，比如，isp[5] 的值是 1，表示 5 是素数；vis 数组同样如此，比如，vis[2] 的值如果为 0 的话，表示 1 到 n 中 2 这个值没有被访问过。但是，A 数组是从 0 开始存储的，从 0 到 n - 1 存储最后生成的可能的情况。
上面的代码在 n = 6 和 n = 8 情况下的测试结果：
6 的情况：
1 4 3 2 5 6
1 6 5 2 3 4
8 的情况：
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2