javascript - 从给定字符串生成所有可能的回文组合 (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>

以上返回:

["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

然后，用 double 中的字符生成每个组合:

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 次，则将其一次添加到 double 中，一次添加到单次中。如果它出现 4 次，将它添加到 double 中，依此类推......(这将创建重复输出；如果您只想要唯一的解决方案，则在生成组合时必须避免重复，并检查最后一个字符在生成回文的同时与单打组合。)

---

这是基本版本的代码示例:

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