javascript - 没有分隔符的数字字母表

Question

例如，如果我们的输入是"1125"，最大值是26，那么我们的输出将是:

[ [1,1,2,5] , [11,2,5] , [1,12,5] , [1,1,25] , [11,25] ]

这是一个数组，由所有可能的方式组成，以将字符分隔为小于值 26。

我们可以使用它来解密已将字母转换为字母数字但没有分隔符的消息。

这是我目前的代码，这是我第一次尝试解决这个问题:

Array.prototype.indexOfArray=function(array){
    for(var i=0;i<this.length;i++){
        if(this[i].length==array.length){
            var same=true;
            for(var j=0;j<this[i].length;j++){
                if(this[i][j]!=array[j]){
                    same=false;
                    break;
                }
            }
            if(same){
                return i;
            }
        }
    }
    return-1;
};
function possibilities(string,max){ //The function I'm talking about.
    var output=[];
    (function collector(array,held,start){
        for(var i=start;i<string.length;i++){
            var char=string[i];
            if(Number(held+char)>max){
                array.push(held);
                held=char;
            }else{
                held+=char;
                if(i!=string.length-1){
                    collector(array.slice().concat(held),"",i+1);
                }
            }
        }
        if(held.length>0){
            array.push(held);
        }
        if(output.indexOfArray(array)==-1){
            output.push(array);
        }
    })([],"",0);
    return output;
}
var message="302213"; //"dawn" is "3 0 22 13" with delimiters
var alphabet="abcdefghijklmnopqrstuvwxyz";
var solutions=possibilities(message,alphabet.length);
for(var i=0;i<solutions.length;i++){
    console.log(solutions[i].join(",")+" : "+solutions[i].map(x=>alphabet[Number(x)]).join(""));
}

然后打印出来:

3,0,2,2,1,3 : daccbd
3,0,2,2,13 : daccn
3,0,2,21,3 : dacvd
3,0,22,1,3 : dawbd
3,0,22,13 : dawn
3,02,2,1,3 : dccbd
3,02,2,13 : dccn
3,02,21,3 : dcvd
3,022,1,3 : dwbd
3,022,13 : dwn

我该如何改进它？这个算法的名字是什么？

Answer 1

您可以使用不同的方法将部分粘合在一起，使用 2^{array.length - 1} 作为不同分块部分的公式。然后过滤掉那些大于25的值。

function split(string) {
    var array = string.split(''),
        result = [],
        i, l = 1 << (array.length - 1),
        v, j,
        temp;

    for (i = 0; i < l; i++) {
        v = i;
        temp = [array[0]];
        for (j = 1; j < array.length; j++) {
            if (v & 1) {
                temp[temp.length - 1] += array[j];
            } else {
                temp.push(array[j]);
            }
            v = v >> 1;
        }
        result.push(temp);
    }
    return result.filter(function (a) {
        return a.every(function (b) {
            return b < 26;
        });
    });
}

function output(array) {
    array.forEach(function (a) {
        console.log(a.join(), a.map(function (b) { return (+b + 10).toString(36); }).join(''));
    });
}

output(split('302213'));
output(split('1125'));

.as-console-wrapper { max-height: 100% !important; top: 0; }