алфавит из цифр без разделителей

Question

Если бы мы имели наш вклад в «1125» и максимальное значение, как , например, наш результат будет:

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

это массив, который состоит любого возможного способа отделить символы от значения .

Мы можем использовать это для расшифровки сообщений, которые были преобразованы в алфавитном порядке, но без разделителей.

Вот мой текущий код, моя первая попытка решить эту проблему:

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; }

Answer 2

это хороший пример рекурсивного подхода. Давайте сделаем несколько определений первых

1. Входной

   ввод строчной строка <'a','z'> кодируется в <1,26> без разделителей.

2. выход

   мы хотим получить все декодирования комбинаций строк для каждого действительного декодирования 1 против 2 цифровых кодов.

3. Эвристика

   так 2 цифры коды могут начинаться с { 1,2 } и { 0 } означает, что мы Handlin 2-значный код { 10,20 } или { 0 } для <0,25> этого могут быть использованы, чтобы снизить количество комбинаций.

Рекурсивный алгоритм

, если у нас есть некоторая функция, как decode(in); то мы можем рекурсивно сделать это простым способом, как это:

decode (string in) 
{ 
l=in.Length(); 
add_combination(tochar(in[1]) + in.substring(2,l-1)); 
add_combination(tochar(10*in[1]+in[2]) + in.substring(3,l-2)); 
} 

В простых словах принимают первый 1 или 2 цифры символа и декодировать остальную часть строки.Пусть Предположим, ваш пример 1125 в рекурсии будет, как это:

||decode(1125)| 
|1|decode(125)| 
    |1,1|decode(25)| 
    |1,1,2|decode(5)| 
    |1,1,2,5|decode()| - combination 
    |1,1,25|decode()| - combination 
    |1,12|decode(5)| 
    |1,12,5|decode()| - combination 
|11|decode(25)| 
    |11,2|decode(5)| 
    |11,2,5|decode()| - combination 
    |11,25|decode()| - combination 

intendation представляют рекурсии слой, первая часть текущей комбинации префикса (in0) и правая часть остальной части строки для декодирования (in1+i).

Это звучит просто, но для кодирования такой обратной связи немного сложнее. Это потому, что нам нужно запомнить список решений вместо одного. Я решил сохранить все результаты в одной строке, разделенной \r\l концом строк. Здесь работает VCL/C++ пример:

//--------------------------------------------------------------------------- 
AnsiString txt_encode0(const AnsiString &in) // <'a','z'> -> <0,25> 
    { 
    int i,l=in.Length(); 
    AnsiString txt=""; 
    for (i=1;i<=l;i++) txt+=int(in[i]-'a'); 
    return txt; 
    } 
//--------------------------------------------------------------------------- 
AnsiString txt_encode1(const AnsiString &in) // <'a','z'> -> <1,26> 
    { 
    int i,l=in.Length(); 
    AnsiString txt=""; 
    for (i=1;i<=l;i++) txt+=int(in[i]-'a'+1); 
    return txt; 
    } 
//--------------------------------------------------------------------------- 
void txt_decode0(AnsiString &out,AnsiString in0,const AnsiString &in1,int i,int &l) // recursion <0,25> -> <'a','z'> 
    { 
    // stop recursion if whole string processed 
    if (i>l) { out+=in0+"\r\n"; return; } 
    int a0,a1; 
    // load first 2 digits from i if second digit is not applicable set is as -1 
       a0=in1[i]-'0'; i++; 
    if (i<= l) a1=in1[i]-'0'; else a1=-1; 
    if (a0> 2) a1=-1; // >2 means always 1 digit code 
    if (a0==0) a1=-1; // =0 means always 1 digit code 
    // one digit combination 
    in0+=char(a0+'a'); 
    txt_decode0(out,in0,in1,i,l); 
    in0.SetLength(in0.Length()-1); 
    // 2 digit combination 
    if (a1>=0) 
     { 
     a0*=10; 
     a0+=a1; i++; 
     if (a0<=26) 
      { 
      in0+=char(a0+'a'); 
      txt_decode0(out,in0,in1,i,l); 
      } 
     } 
    } 
AnsiString txt_decode0(const AnsiString &in) // <0,25> -> <'a','z'> 
    { 
    int l=in.Length(); 
    AnsiString in0="",out=""; 
    txt_decode0(out,in0,in,1,l); 
    return out; 
    } 
//--------------------------------------------------------------------------- 
void txt_decode1(AnsiString &out,AnsiString in0,const AnsiString &in1,int i,int &l) // recursion <1,26> -> <'a','z'> 
    { 
    // stop recursion if whole string processed 
    if (i>l) { out+=in0+"\r\n"; return; } 
    int a0,a1; 
    // load first 2 digits from i if second digit is not applicable set is as -1 
       a0=in1[i]-'0'; i++; 
    if (i<=l) a1=in1[i]-'0'; else a1=-1; 
    if (a0> 2) a1=-1; // >2 means always 1 digit code 
    // one digit combination 
    if (a1!=0)   // =0 means always 2 digit code 
     { 
     in0+=char(a0+'a'-1); 
     txt_decode1(out,in0,in1,i,l); 
     in0.SetLength(in0.Length()-1); 
     } 
    // 2 digit combination 
    if (a1>=0) 
     { 
     a0*=10; 
     a0+=a1; i++; 
     if (a0<=26) 
      { 
      in0+=char(a0+'a'-1); 
      txt_decode1(out,in0,in1,i,l); 
      } 
     } 
    } 
AnsiString txt_decode1(const AnsiString &in) // <1,26> -> <'a','z'> 
    { 
    int l=in.Length(); 
    AnsiString in0="",out=""; 
    txt_decode1(out,in0,in,1,l); 
    return out; 
    } 
//--------------------------------------------------------------------------- 
void main() 
    { 
    AnsiString enc,dec,txt; 
    txt="decoding"; 
    enc=txt_encode0(txt); 
// enc="302213"; 
    dec=txt_decode0(enc); 
    } 
//--------------------------------------------------------------------------- 

txt_encode0,txt_decode0 работает на <0,25> и txt_encode1,txt_decode1 работает на <1,26> диапазоне.

out содержит список допустимых комбинаций. in0 содержит фактический префикс комбинации in1. i - начальный индекс фактической комбинации в in1 и l - длина in1. Здесь выход для <0,25>:

message:decoding 
encoded:3421438136 
decoded in [ 0.013 ms] 

decbedibdg 
decbeding 
decodibdg 
decoding 
devedibdg 
deveding 

и ваш образец:

encoded:302213 
decoded in [ 0.007 ms] 

daccbd 
daccn 
dacvd 
dawbd 
dawn 

Я использую AnsiString из VCL они само распределение динамических строк с индексацией из 1. Например AnsiString s="abc";s[1]=='a' Размер s.Length()s[s.Length()]=='c'.

Answer 3

Рекурсивный подход в JavaScript. Идея состоит в том, что следующие два символа в строке могут быть интерпретированы двумя способами, добавьте каждый из двух способов к каждому результату при расщеплении следующей части строки. В противном случае добавьте только первый символ к каждому результату в разделении следующей части строки.

function possibilities(str){ 
 
    if (str.length === 0) return [[]]; 
 
    
 
    var result = [], next = possibilities(str.substr(1)); 
 
     
 
    for (var i=0; i<next.length; i++) 
 
    result.push([str[0]].concat(next[i])); 
 

 
    if (str.length > 1 && str[0] !== '0' && str.substr(0,2) < 27){ 
 
    next = possibilities(str.substr(2)); 
 
     
 
    for (var i=0; i<next.length; i++) 
 
     result.push([str.substr(0,2)].concat(next[i])); 
 
    } 
 
    
 
    return result; 
 
} 
 

 
console.log(possibilities('1125')); 
 
console.log(possibilities('302213'));