当我的 Johnson-Trotter 算法中没有打印语句时，为什么会出现分段错误？

Question

我正在尝试用 C++ 实现 Johnson-Trotter 算法来完成家庭作业。在（我认为）我弄明白之后我真的很兴奋，但结果是当我运行它时我遇到了段错误。这是它的代码（抱歉有点长）：

#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 isMobile\n";
    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 isMobile\n";
    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 factorial\n";
    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 hasMobile\n";
    while (hasMobile(permutations[permutation], n)) {
        cout << "Before setNextPermutation\n";
        setNextPermutation(permutations[permutation], permutations[permutation + 1], n);
        permutation++;
        cout << "Before largestMobile\n";
        int k = largestMobile(permutations[permutation], n);
        cout << "Before swapMobile\n";
        swapMobile(permutations[permutation], k);
        cout << "Before reverseArrows\n";
        reverseArrows(permutations[permutation], n, k);
    }

    cout << "Before printPermutation\n";
    for (int i = 0; i < nFactorial; i++) {
        printPermutation(permutations[i], n);
        cout << ' ';
        if (!((i + 1) % n))
            cout << '\n';
    }
}

int main() {
    JohnsonTrotter(N);

    return 0;
}

我首先运行它没有任何打印语句，它给了我一个段错误。我输入了一些打印语句，但没有出现段错误，但也没有得到预期的结果。我删除了 print 语句，将 N 更改为 2，并再次出现段错误。我将 N 更改为 1 并得到了预期的结果。我将 N 更改为 4，并且在有和没有打印语句的情况下都出现了段错误。

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

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 也需要更新。

当我的 Johnson-Trotter 算法中没有打印语句时，为什么会出现分段错误？

Why do I get a segmentation fault when I don't have print statements in my Johnson-Trotter algorithm?

c++

algorithm