Why is my permutation code generating duplicates?-CodePudding

My code is generating duplicates (3) to be precise and I don't know why, could anyone help out? I've tried searching for a problem, but to my eyes it seems the same as other premutation codes on the internet.

I was thinking it could've been a miss-use of the loop but I don't see why it's giving me 9 answers instead of 6.

#include <iostream>
using namespace std;

void swap(char *a, int x, int y);
void print(char *a, int n);
void permute(char *a, int n, int index);
int grabSize(char a[]);

int main() {
    char array[] = {'a', 'b', 'c'}; // PLACE COMPONENTS HERE
    int n = grabSize(array);

    //

    cout << "[" << endl;
    cout << "   ";
    permute(array, n, 0);
    cout << endl << "]";
}

int grabSize(char a[]) {
    int i = 0;
    while (a[i] != '\0') {
        i  ;
    }
    return i;
}

void swap(char *a, int x, int y) {
    char aux;
    aux = a[x];
    a[x] = a[y];
    a[y] = aux;
}

void permute(char *a, int n, int index) {
    if (index == n-1) {
            print(a, n);
            return;
    }
    for (int i = 0; i < n; i  ) {
        swap(a, i, index);
        permute(a, n, index 1);
        swap(a, i, index);
    }
}

void print(char *a, int n) {
    cout << " [ ";
    for (int i = 0; i < n; i  ) {
        cout << a[i];
    }
    cout << " ] ";
}

CodePudding user response：

You are getting 9 combinations of string because, in permute(), the for loop variable i initialised with 0:

for (int i = 0; i < n; i  ) {
            ^^^

Note that you are calling permute() function recursively to generate the permutations of string and, in every recursive call, the index is incremented by 1 while passing to permute() function but the for loop , in permute() function, starts with 0 and iterate till < n. Hence you are getting n*n combinations of string in output. Instead, the for loop variable i should be initialised with index:

    for (int i = index; i < n; i  ) {
                 ^^^^^

Other problems in your code:

This

char array[] = {'a', 'b', 'c'};

is array of 3 characters. Note that there is no terminating null character in array array. Passing it to grabSize() function and checking for '\0' character in it will lead to UB as grabSize() function will end up accessing array array beyond its size while looking for null terminating character. To get the size of array, you can simply do sizeof(array)/sizeof(array[0]) in main() function and do away with grabSize() function.

If you are inclined to use grabSize() function then either add null terminating character manually

char array[] = {'a', 'b', 'c', '\0'};

or initialise array array with string, like this

char array[] = "abc";

and then pass it to grabSize() function.

Suggestion:

In C , the use of plain C style array is discouraged. C has Containers Library, go through it. The sequence container array and vector will be of your interest.