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"]
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:
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 → " + palindromeCombinations("rarerara"));