optimization algorithm palindrome [closed]

Question

how to make this algorithm to display palindrome that was done with fewer permutations ?

#include <bits/stdc++.h>
    using namespace std;
    #define M 26


    bool isPalin(string str, int* freq)
    {

        memset(freq, 0, M * sizeof(int));
        int l = str.length();


        for (int i = 0; i < l; i++)
            freq[str[i] - 'a']++;

        int odd = 0;


        for (int i = 0; i < M; i++)
            if (freq[i] % 2 == 1)
                odd++;


        if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
            return true;
        else
            return false;
    }


    string reverse(string str)
    {
        string rev = str;
        reverse(rev.begin(), rev.end());
        return rev;
    }


    void printAllPossiblePalindromes(string str)
    {
        int freq[M];

        // checking whether letter can make palindrome or not
        if (!isPalin(str, freq))
            return;

        int l = str.length();


        string half = "";
        char oddC;
        for (int i = 0; i < M; i++)
        {
            /* This condition will be true at most once */
            if(freq[i] % 2 == 1)
                oddC = i + 'a';

            half += string(freq[i] / 2, i + 'a');
        }




        do
        {
            palin = half;
            if (l % 2 == 1)
                palin += oddC;
            palin += reverse(half);
            cout << palin << endl;
        }
        while (next_permutation(half.begin(), half.end()));
    }


    int main()
    {
        string str = "trtaccart";
        cout << "All palindrome permutations of " << str << endl;
        printAllPossiblePalindromes(str);
        return 0;
    }

Answer 1

Conceptually, your code is pretty good though there are a few design an language features that can be used.

First, you use #include <bits/stdc++.h> which I am unfamiliar with but I'm assuming includes a few appropriate standard C++ libraries. However, the standard C++ way would be to include each library as needed

#include <string>    // std::string
#include <iostream>  // std::cout
#include <algorithm> // std::reverse, std::next_permutation

There are many posts that warn programmers about using using namespace std; (link) as well as using #define statements for constants (link). Though the biggest gain would probably be from renaming it from M to something like ALPHABET_SIZE (single letter variable names are often confusing).

Your function name isPalin is slightly confusing because it doesn't check if the string IS a palindrome but rather CAN IT BE a palindrome.

One thing that can affect performance greatly is to reduce unneeded copying. Your function signature bool isPalin(string str, int* freq) introduces a copy from the calling function into the str variable. Because this and all your functions just work based on the string and don't change it, this could be replaced by const std::string&

This first thing your isPalin function does is clear the freq array. But the C++ way to do it would be to clear it in the initialization like so:

int freq[M] = {}; // the {} initializes the whole array to 0

or the even more C++ way would be to use std::array:

std::array<int, M> freq; 

and change your function to

bool isPalin(const std::string& str, std::array<int, ALPHABET_SIZE>& freq)

Another thing, I'd advise against using l to denote the string length (again because one letter variable names are confusing) and would encourage you to simply use str.size()

The construct

if (<code>)
    return true;
else
    return false:

is the same thing as

return <code>;

Everything else here is just a few optimizations. In printAllPossiblePalindromes you could call half.reserve(str.size()/2) to avoid needless reallocations. In std::string half = "", setting it to the empty string doesn't actually do anything here.

your code here:

    palin = half;
    if (l % 2 == 1)
        palin += oddC;
    palin += reverse(half);
    cout << palin << endl;

doesn't actually need to build palin because it's only being printed. So you can do

    if (str.size() % 2 == 0)
        std::cout << half << reverse(half) << std::endl;
    else
        std::cout << half << oddC << reverse(half) << std::endl;

Answer 2

Nitpicks

    using namespace std;

You may want to read Why is using namespace std bad practice?

    #define M 26

This would be more readable as something like

    #define ALPHABET_SIZE 26

And this is C++, so it would be better written as

    constant int ALPHABET_SIZE = 26;

This will enforce type safety as well.

More naming

    bool isPalin(string str, int* freq)

I would find this more readable as

    bool canBePalindrome(std::string candidate, int* letterCounts)

Not only does that write out palindrome so that you don't need to remember that that is what you meant, it better describes what you are asking. It's not if the string is currently a palindrome, it's if the string could be a palindrome.

I prefer the names candidate and letterCounts. Both because they are written out and because they (in my opinion) better describe the variables.

You can see here how it is clearer that string is in namespace std. In your original code, that wasn't nearly as obvious.

Write robustly in the face of future edits

        memset(freq, 0, M * sizeof(int));

It would be better to write

        memset(letterCounts, 0, ALPHABET_SIZE * sizeof(*letterCounts));

That way, if you change the type of letterCounts to something else in the future, this will change automatically with it. In your original code, you could end up clearing memory outside the array or not clearing all the array if you changed the type to short * or long *. By using the name, you ensure that won't happen. It will always use the right type.

Favor range-based for loops

        for (int i = 0; i < l; i++)
            freq[str[i] - 'a']++;

Rather than managing the loop manually, you can use the C++ for each form:

        for (char &c : candidate)
        {
            characterCounts[c - 'a']++;
        }

It is usually recommended to always use the block form of control structures even when you currently only have a single statement. This helps clarify what is and is not supposed to be in the loop.

Don't Repeat Yourself (DRY)

        if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
            return true;
        else
            return false;

You could more easily write this as

        // if there are an even number of letters in the candidate
        // then it can only be formed into a palindrome if all characterCounts are even
        // or if there are an odd number of letters there must be only one letter 
        // with an odd number of occurrences
        return candidate.length() % 2 == oddCount;

That gets rid of the l variable entirely (only used once in the revised code).

Saying oddCount rather than odd makes it clearer that we are counting.

We can return true or false directly, so we don't need to use the if/else construct.

We don't need two different clauses based on whether the length is odd or even. In both cases, oddCount should match the remainder.

Single Responsibility Principle

        if (!isPalin(str, freq))
            return;

I'd break your original functions into two:

        countLetters(str, letterCounts);
        if (! canBePalindrome(str, letterCounts))
        {
            return;
        }

Now there is one function that generates the letterCounts and another function that uses them. This saves us having side effects to a function that returns a Boolean value. The side effect (generating the letterCounts) is now in a function that clearly has that purpose.

Keep it simple

If you change

       char oddC;

to

        char oddC = 0;

then

            palin = half;
            if (l % 2 == 1)
                palin += oddC;
            palin += reverse(half);
            cout << palin << endl;

could be simpler

            std::cout << half << oddC << reverse(half) << std::endl;

Now you don't need palin at all, which is good since you don't declare it.

Do you just need the count?

In one of the comments, you say

I want to see the minimum number of permutations of a word so that it becomes a palindrome but do not know how to do that .

If all you need is the count, then the code could be much simpler:

        int letterCounts[ALPHABET_SIZE] = {};

        countLetters(str, letterCounts);
        if (!canBePalindrome(str, letterCounts))
        {
            std::cout << "No palindromes can be made from '" << str << "'." << std::endl;
            return;
        }

        int palindromeCount = factorial(str.length() / 2);
        for (int i = 0; i < M; i++)
        {
            freq[i] /= 2;
            palindromeCount /= factorial(letterCounts[i]);
        }

        std::cout << "Number of unique palindromes that can be made from '" << str << "':  " << palindromeCount << std::endl;

Note that this assumes that your factorial results stay within the bounds that can be stored in an int.

This works because a factorial is simply the number of orderings of a certain number of elements. We divide by factorial(letterCounts[i]) because duplicate letters are not ordered. So we divide out the number of orderings there would be if the duplicate letters had been distinguishable characters. Note that oddC is always in the same place if there, so we don't need to count it (integer rounding after division handles that). We only need to count the number of orderings of the first half of the string because it's a palindrome. There's always just one ordering of the second half that will match the first half.

    int factorial(int n)
    {
        int result = 1;

        while (n > 1)
        {
            result *= n--;
        }

        return result;
    }

This is an example of how the factorial function might be written. You can change the return type to unsigned long or bigger if you start having overflow.

If you actually need the palindromes listed, I don't see how you could do it in fewer iterations. The std::next_permutation already guards against duplicate strings. You have to go through that loop at least once per palindrome.