为什么当我的约翰逊-特罗特算法中没有打印语句时，会出现分割错误？

Question

我正试图在C++中为一项家庭作业实现Johnson Trotter算法。在(我想(我找到它之后，我真的很兴奋，但事实证明，当我运行它时，我遇到了seg错误。以下是它的代码(对不起，它有点长(：

#include <iostream>
#define N   3
#define RIGHT   true
#define LEFT    false
using namespace std;
// Struct to represent a number with its arrow and its mobility
struct number {
int num;
bool arrow;
};
void printPermutation(number permutation[], int n) {
for (int i = 0; i < n; i++) {
if (permutation[i].arrow == LEFT)
cout << '-';
cout << permutation[i].num << ' ';
}
}
void reverseArrows(number permutation[], int n, int k) {
for (int i = 0; i < n; i++)
if (permutation[i].num > permutation[k].num)
permutation[i].arrow ^= 1;
}
void swapMobile(number permutation[], int k) {
number temp;
temp.num = permutation[k].num;
temp.arrow = permutation[k].arrow;
int swapper;
if (permutation[k].arrow == RIGHT)
swapper = 1;
else    // permutation[k].arrow == LEFT
swapper = -1;
permutation[k].num = permutation[k + swapper].num;
permutation[k].arrow = permutation[k + swapper].arrow;
permutation[k + swapper].num = temp.num;
permutation[k + swapper].arrow = temp.arrow;
}
void setNextPermutation(number current[], number next[], int n) {
for (int i = 0; i < n; i++) {
next[i].num = current[i].num;
next[i].arrow = current[i].arrow;
}
}
bool isMobile(number permutation[], int n, int k) {
if ((k == 0) && (permutation[k].arrow == LEFT))
return false;
if ((k == n - 1) && (permutation[k].arrow == RIGHT))
return false;
if ((permutation[k].arrow == LEFT) && (permutation[k - 1].num < permutation[k].num))
return true;
if ((permutation[k].arrow == RIGHT) && (permutation[k].num > permutation[k + 1].num))
return true;
return false;
}
int largestMobile(number permutation[], int n) {
int largest = 0;
cout << "Before isMobilen";
for (int i = 1; i < n; i++)
if (i > largest && isMobile(permutation, n, i))
largest = i;
return largest;
}
bool hasMobile(number permutation[], int n) {
cout << "Before isMobilen";
for (int i = 0; i < n; i++)
if (isMobile(permutation, n, i))
return true;
return false;
}
// Simple function to iteratively calculate n!
int factorial(int n) {
int factorial = 1;
for (int i = 1; i <= n; i++)
factorial *= i;
return factorial;
}
void JohnsonTrotter(int n) {
cout << "Before factorialn";
int nFactorial = factorial(n);
number permutations[nFactorial][n];
// Initialize first permutation.
for (int i = 0; i < n; i++) {
permutations[0][i].num = i + 1;
permutations[0][i].arrow = LEFT;
}
int permutation = 0;
cout << "Before hasMobilen";
while (hasMobile(permutations[permutation], n)) {
cout << "Before setNextPermutationn";
setNextPermutation(permutations[permutation], permutations[permutation + 1], n);
permutation++;
cout << "Before largestMobilen";
int k = largestMobile(permutations[permutation], n);
cout << "Before swapMobilen";
swapMobile(permutations[permutation], k);
cout << "Before reverseArrowsn";
reverseArrows(permutations[permutation], n, k);
}
cout << "Before printPermutationn";
for (int i = 0; i < nFactorial; i++) {
printPermutation(permutations[i], n);
cout << ' ';
if (!((i + 1) % n))
cout << 'n';
}
}
int main() {
JohnsonTrotter(N);
return 0;
}

我第一次运行它时没有任何打印语句，它给了我一个seg错误。我加入了一些打印语句，我没有得到seg错误，但我也没有得到预期的结果。我删除了print语句，将N更改为2，然后再次出现seg错误。我将N更改为1，得到了预期的结果。我将N更改为4，并在包含和不包含print语句的情况下出现seg错误。

此外，如果这是错误的提问方式，我很抱歉，但我以前从未在这里问过任何问题。

Answer 1

感谢所有响应的人。你们都是对的，试图访问的元素比为数组分配的内存还多。我在largestMobile函数中找到了罪魁祸首。以下是重构后的代码：

int largestMobile(number permutation[], int n) {
int k = 0;
while (!isMobile(permutation, n, k))
k++;
if (k < n - 1)
for (int i = k + 1; i < n; i++)
if (permutation[i].num > permutation[k].num && isMobile(permutation, n, i))
k = i;
return k;
}

小(明显(注意：我将变量名largest改为仅k，以便在一行中腾出更多空间，这也是有意义的，因为这就是我无论如何都要返回的内容。我最后检查了一下我要返回的元素是否是移动的。以前的版本从未检查largest是否是移动的。同样在以前的版本中，如果permutation中最大的元素在数组的前面，则没有其他元素可能更大，因此largest从未更新。

此外，在swapMobile中，k也需要更新。