string_palidrome_permutations.cpp

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cstring>
#include <cmath>
#include <numeric>

using namespace std;


#define fori(i,a,b) for(int i=a; i<=b; ++i)
#define ford(i,a,b) for(int i=a; i>=b; --i)
#define rep(i,n) for(int i=0; i<n; ++i)
#define prnt(str) cout << str << endl
#define sz(x) (int)x.size()

typedef long long ll;
void generate_perm(string&, int, vector<string>&);

template<class T>
string to_string(T input) {
    stringstream ss;
    ss << input;
    cout << ss.str() << endl;
    return ss.str();
}

void generate_palidromes(string &str) {
    map<char, int> mc;
    rep(i, str.length()) {
        mc[str[i]]++;
    }

    map<char, int>::iterator it;
    vector<char> pal_vec;
    for(it=mc.begin(); it!=mc.end(); ++it) {
        int n = ceil(it->second/2);
        rep(i,n) {
            pal_vec.push_back(it->first);
        }
    }

    if (pal_vec.size() == 0) {
        prnt("No even/odd palindromes of length >1 exists.\nAll palidromes are of single character");
        rep(i,str.length()) {
            prnt(str[i]);
        }
        return;
    }

    string pal_str(pal_vec.begin(), pal_vec.end());
    prnt("Palidrome string = " << pal_str);
    vector<string> res;
    res.push_back(pal_str); //pushing current string itself
    generate_perm(pal_str, pal_str.length()-1, res);

    rep(i, sz(res)) {
        // even palidrome
        string tmp_res = res[i]+res[i];
        prnt(tmp_res);

        // odd palidromes
        for(it=mc.begin(); it!=mc.end(); ++it) {
            if (it->second%2==1) {
                string tmp_res_1 = res[i] + to_string(it->first) + res[i];
                prnt(tmp_res_1);
            }
        }
    }
}


void generate_perm(string &str, int ind, vector<string> &res) {
    if (ind == 0) {
        //prnt("Generated perm = " << str);
        res.push_back(str);
        return;
    }

    //prnt(str << " = " << ind);
    // either delete at index or swap with all indexes.

    // delete
    string str1 = str;
    if (ind <= str.length()-1) {
        str1.erase(ind,1);
        generate_perm(str1, ind--, res);
    }

    // swap
    fori(i,0, str.length()-1) {
        string tmp_str = str;
        if (tmp_str[i] != tmp_str[ind]) {
            swap(tmp_str[i], tmp_str[ind]);
            generate_perm(tmp_str, ind--,res);
        }
    }

    //same string with no alteration
    string tmp_str = str;
    //generate_perm(tmp_str,ind--,res);
}

int main() {
    string str;
    cin >> str;
    //vector<string> res;
    //generate_perm(str, str.length()-1,res);
    //sort(res.begin(), res.end());
    generate_palidromes(str);
    
    return 0;
}