从给定字符串生成所有可能的回文组合 (Javascript)

Question

我有一个字符串 'racecarzz'，我想从该字符串中生成每个字符的所有可能组合，这些字符可以以相同的方式前后读取（回文）。

检查回文不难string.split('').reverse().join('')但生成可能的组合对我来说非常具有挑战性。

输入：

str = 'racecarzz'

输出：

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

我已经尝试了 get-all-combinations-for-a-string 的解决方案，但它仍然缺少一些像 'zracecarz'、'raczezcar' 等...

    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>

以上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"]

参考：https://jsfiddle.net/f77g15tx/1/

Answer 1

如果您只想生成回文（无需首先生成所有字符的所有可能组合，然后过滤掉非回文），请将输入中的字符分成两组，具体取决于频率它们发生：

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 ...

不要忘记自己添加单个字符； "e"也是回文。

如果一个字符出现 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 &rarr; " + 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"));

从给定字符串生成所有可能的回文组合 (Javascript)

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

javascript

string

algorithm

permutation

palindrome