CODEWITHSUNDEEP
c++arraysrecursiondata-structurespermutation
user11555625
user11555625

Reputation:

Why am i getting output for permutations of a string of length only 3?

Print Permutations - String

Given a string, find and print all the possible permutations of the input string. Note : The order of permutations are not important. Just print them in different lines.

Sample Input :

abc

Sample Output :

abc acb bac bca cab cba

#include <iostream>
#include <string>
using namespace std;

void printCurrentString(string input, string result, int count[], int level)
{
    if (level == input.size())
    {
        cout << result << endl;
        return;
    }
    else
    {
        for (int i = 0; i < input.size(); i++)
        {
            if (count[i] == 0)
                continue;
            else
            {
                result[level] = input[i];
                count[i]--;
                printCurrentString(input, result, count, level + 1);
                count[i]++;
            }
        }
    }
}

void printPermutations(string input)
{
    char *result = new char[input.size()];
    int *count = new int[input.size()];
    for (int i = 0; i < input.size(); i++)
        count[i] = 1;
    printCurrentString(input, result, count, 0);
}

int main()
{
    string input;
    cin >> input;
    printPermutations(input);
    return 0;
}

Upvotes: 0

Views: 73

Answers (1)

Some programmer dude
Some programmer dude

Reputation: 409176

Two major problems, both leading to undefined behavior:

First from the printPermutations function:

char *result = new char[input.size()];

As mentioned in my comment, this will allocate memory but not initialize it in any way. Creating a std::string from this memory is one cause of UB (Undefined Behavior).

The second is in the printCurrentString function, where you have

result[level] = input[i];

Since you don't know the actual size of the the string in result you don't know if level is a valid index. It could be out of bounds. Indexing out of bounds also leads to UB.

You can solve both of these issues with a simple change: In the printPermutations function don't create the result string dynamically the way you do. Instead create a proper std::string object of the correct length and pass it:

printCurrentString(input, string(input.length()), count, 0);

And considering the memory leaks you have (you don't delete[] the memory you new[]) I would also recommend you use a std::vector<int> for count, and that you pass this vector by reference.

Upvotes: 0

Related Questions