Generate all possible combinations that are palindrome from a given string (Javascript)

Question

I have a string 'racecarzz' and I would like to generate all possible combinations of each character from that string that can be read the same way backward and forward (Palindrome).

Check for Palindromes is not difficult string.split('').reverse().join('') but generating the possible combinations is quite challenging for me.

input:

str = 'racecarzz'

output:

arr = ['rar', 'cec', 'raar', 'caac', 'craarc', 'racecar', 'raczezcar', 'zracecarz', ...]`

I've tried the solution for get-all-combinations-for-a-string but it's still missing some like 'zracecarz', 'raczezcar', etc...

    var combinations = function (string) {
    var result = [];
    var loop = function (start,depth,prefix) {
        for (var i=start; i<string.length; i++) {
            var next = prefix+string[i];
            if (depth > 0) {
                loop(i+1,depth-1,next);
            } else {
                //check for Palindrome
                if (next == next.split('').reverse().join('')) {
                    result.push(next);
                }
            }
        }
    }
    for (var i=0; i<string.length; i++) {
        loop(0,i,'');
    }
    //remove duplicate
    result = result.filter(function(val, ind){
      return result.indexOf(val)==ind;
    });
    return result;
}
document.querySelector('#demo').innerHTML = combinations('racecarzz').join('<br>');

<div id="demo"></div>

Above returns:

["r", "a", "c", "e", "c", "a", "r", "z", "z", "rr", "aa", "cc", "zz", "rar", "rcr", "rer", "rcr", "rar", "aca", "aea", "aca", "cec", "raar", "rccr", "acca", "racar", "raear", "racar", "rcecr", "aceca", "raccar", "racecar"]

Ref: https://jsfiddle.net/f77g15tx/1/

Answer 1

If you want to generate just the palindromes (without first having to generate every possible combination of all the characters and then filtering out the non-palindromes), split the characters in the input into two groups, depending on how often they occur:

input:   racecarzz
singles: e
doubles: carz

Then, generate every combination with characters from doubles:

c, a, r, z, ca, cr, cz, ac, ar, az ... zrca, zrac  

Then, with each of these combinations, create 3 palindromes: one without repeating the last character, one repeating the last character, and one with the single character in the middle:

c    -> c, cc, cec
ca   -> cac, caac, caeac
car  -> carac, carrac, carerac
carz -> carzrac, carzzrac, carzezrac
...

If there are more than one singles, create palindromes with each of these singles:

car -> carac, carrac, carerac, carfrac, cargrac ...  

Don't forget to add the single characters by themselves; "e" is also a palindrome.

If a character occurs 3 times, add it once to the doubles and once to the singles. If it occurs 4 times, add it twice to the doubles, and so on... (This will create duplicate output; if you only want unique solutions, you'll have to avoid duplicates while generating the combinations, and check the last character in combinations against the singles while generating the palindromes.)

---

This is a code example of the basic version:

function splitInput(str) {
    var singles = [], doubles = [];
    for (var i in str) {
        var char = str.charAt(i);
        var pos = singles.indexOf(char);               // check if already in singles
        if (pos == -1) singles.push(char);             // add to singles
        else doubles.push(singles.splice(pos, 1)[0]);  // move to doubles
    }
    return {singles: singles, doubles: doubles};
}

function generateCombinations(set) {
    var combis = [];
    addChar([], set);               // start recursion with empty partial and full set
    return combis;

    function addChar(partial, set) {
        for (var i in set) {
            var setCopy = set.slice();
            var parCopy = partial.concat(setCopy.splice(i, 1)); // add char to partial
            combis.push(parCopy);
            if (setCopy.length) addChar(parCopy, setCopy);    // recurse if chars left
        }
    }
}

function generatePalindromes(combis, singles) {
    var palins = singles.slice();                      // each single is a palindrome
    for (var i in combis) {
        var pos = combis[i].length;
        var pal = combis[i].concat([' ']);             // add space for single
        pal = pal.concat(combis[i].reverse());         // add reverse
        for (var j in singles) {
            pal.splice(pos, 1, singles[j]);            // insert single in the middle
            palins.push(pal.join(''));
        }
        pal.splice(pos, 1); palins.push(pal.join('')); // remove single
        pal.splice(pos, 1); palins.push(pal.join('')); // remove repeated last char
    }
    return palins;
}

function palindromeCombinations(input) {
    var sets = splitInput(input);
    var combis = generateCombinations(sets.doubles);
    return generatePalindromes(combis, sets.singles);
}

document.write("racecarzz → " + palindromeCombinations("racecarzz"));

If characters can occur 3 or more times in the input, and you want to generate only unique solutions, adapt the code to:

• When generating the combinations, skip duplicate characters when iterating over the set.
• When generating the palindromes, skip the one without repeated last character if that last character is one of the singles.

This requires just a few lines to be changed:

function splitInput(str) {
    var singles = [], doubles = [];
    for (var i in str) {
        var char = str.charAt(i);
        var pos = singles.indexOf(char);               // check if already in singles
        if (pos == -1) singles.push(char);             // add to singles
        else doubles.push(singles.splice(pos, 1)[0]);  // move to doubles
    }
    return {singles: singles, doubles: doubles};
}

function generateCombinations(set) {
    var combis = [];
    addChar([], set);               // start recursion with empty partial and full set
    return combis;

    function addChar(partial, set) {
        for (var i = 0; i < set.length; i++) {              // instead of for i in set
            if (set.indexOf(set[i]) != i) continue;       // skip duplicate characters
            var setCopy = set.slice();
            var parCopy = partial.concat(setCopy.splice(i, 1)); // add char to partial
            combis.push(parCopy);
            if (setCopy.length) addChar(parCopy, setCopy);    // recurse if chars left
        }
    }
}

function generatePalindromes(combis, singles) {
    var palins = singles.slice();                      // each single is a palindrome
    for (var i in combis) {
        var pos = combis[i].length;
        var pal = combis[i].concat([' ']);             // add space for single
        pal = pal.concat(combis[i].reverse());         // add reverse
        for (var j in singles) {
            pal.splice(pos, 1, singles[j]);            // insert single in the middle
            palins.push(pal.join(''));
        }
        pal.splice(pos, 1); palins.push(pal.join('')); // remove single
        if (singles.indexOf(pal.splice(pos, 1)[0]) == -1) { // if last not in singles
            palins.push(pal.join(''));                 // without repeated last char
        }
    }
    return palins;
}

function palindromeCombinations(input) {
    var sets = splitInput(input);
    var combis = generateCombinations(sets.doubles);
    return generatePalindromes(combis, sets.singles);
}

document.write("rarerara &rarr; " + palindromeCombinations("rarerara"));