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

user_18639018 0
Viewed 73

I'm trying to implement the Johnson-Trotter algorithm in C++ for a homework assignment. I was really excited after (I thought) I figured it out, but as it turns out I get a seg fault when I run it. Here's the code for it (sorry it's a little long):

#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;
}

I first ran it without any print statements and it gave me a seg fault. I threw in some print statements and I didn't get a seg fault, but I didn't get my expected results either. I removed the print statements, changed N to 2, and got a seg fault again. I changed N to 1 and got an expected result. I changed N to 4 and got a seg fault with and without print statements.

Also, sorry if this is the wrong way to ask this but I've never asked a question on here before.

algorithm c++
1 Answers

Thank you to everyone who responded. You all were right about it trying to access more elements than there was memory allocated for the array. I found the main culprit in my largestMobile function. Here is the refactored code:

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;
}

Small (obvious) note: I changed the variable name largest to just k to make more room on one line and also it makes sense since that's what I'll be returning anyway. I finally checked to see whether the element I would be returning is mobile. The previous version never checked if largest was mobile or not. Also in the previous version, if the largest element in permutation was in the front of the array, no other element could possibly be larger and so largest was never updated.

Also, in swapMobile, k needed to be updated as well.

user_186390180
Related