Генерировать все возможные комбинации, которые являются палиндромом из заданной строки (Javascript)

Если вы хотите генерировать только палиндромы (без необходимости сначала генерировать все возможные комбинации всех символов, а затем отфильтровывать непалиндромы), разделите символы во входных данных на две группы в зависимости от того, как часто они встречаются:

input:   racecarzz
singles: e
doubles: carz

Затем сгенерируйте каждую комбинацию с символами из двойников:

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

Затем с помощью каждой из этих комбинаций создайте 3 палиндрома: один без повторения последнего символа, другой с повторением последнего символа. символ, и один с единственным символом в середине:

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

Если существует более одного сингла, создайте палиндромы с каждым из этих синглов:

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

Не забудьте добавить отдельные символы сами по себе; "Е" также является палиндромом.

Если символ встречается 3 раза, добавьте его один раз к парным и один раз к одиночным. Если это происходит 4 раза, добавьте его дважды в двойники и так далее... (Это создаст дублирующиеся выходные данные; если вам нужны только уникальные решения, вам придется избегать дубликатов при создании комбинаций и проверять последний символ в комбинациях против одиночных символов при создании палиндромов.)

---

Это пример кода базовой версии:

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"));

Если символы могут встречаться 3 или более раз во входных данных, и вы хотите генерировать только уникальные решения, адаптируйте код к:

• при создании комбинаций пропускайте повторяющиеся символы при повторении набор.
• при создании палиндромов пропустите один без повторяющегося последнего символа, если этот последний символ является одним из одиночных.

Для этого нужно изменить всего несколько строк:

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"));