Heap's algorithm in C++ repeating?

Question

I am trying to implement Heap's algorithm in C++.
However, the algorithm starts to repeat if the string it's permuting gets to a length of 4. Here's the code:

void permute(int n, string str, int *total,string array[]){

    if (n==0){
        
        array[*total] = str;
        *total += 1;
    
    }

    else{
    
        for(int c=0; c<=n;c++){
            
            permute(n-1,str,total, array);
            if (n % 2 == 0){
                char tmpstr=str[c];
                str[c]=str[n];
                str[n]=tmpstr; 
                }
            else{
                char tmpstr=str[0];
                str[0]=str[n];
                str[n]=tmpstr;
            }
        }
    }
}

int main() {
    int total = 0;
    string array[24];
    permute(3,"abcd",&total, array);
    cout << total << endl;
    return 0;
}

And here is the output. It repeats at the 13th line

24
abcd
bacd
cbad
bcad
cabd
acbd
dbca
bdca
cbda
bcda
cdba
dcba
abcd <-- right here
bacd
cbad
bcad
cabd
acbd
dbca
bdca
cbda
bcda
cdba
dcba

Thank you guys and any help is welcome!

Answer 1

While it is always an excellent idea to use the standard function recommended by PaulMcKenzie, you have posted a code with a question about why it doesn't work.

In your for loop, get rid of the line if (n%2 ==0) and its else part:

  for(int c=0; c<=n;c++){
        permute(n-1,str,total, array);
        char tmpstr=str[c];
        str[c]=str[n];
        str[n]=tmpstr; 
        }

It should then work.