Javascript для вариаций с повторением (комбинаторика) отсутствующих символов строки

Question

Вопрос, аналогичный THIS вопросу, на который еще не был дан ответ.

Как я могу сделать свой код (или любой код javascript, который может быть предложен?) Найти все возможные решения известной длины строки с несколькими недостающими символами в вариации с повторением?

Я пытаюсь взять строку известных длин символов и найти отсутствующие символы из этой строки. Например:

var missing_string = "ov!rf!ow"; //where "!" are the missing characters 

Я надеялся запустить скрипт с определенным массивом, например:

var r = new Array("A","B","C","D","E","F","G","H","I","J","K", 
        "L","M","N","O","P","Q","R","S","T","U","V", 
        "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9); 

Чтобы найти все возможные варианты с повторением тех недостающих символов, чтобы получить результат:

ovArfAow 
ovBrfAow 
ovCrfAow 
... 
ovBrfBow 
ovBrfCow 
... 
etc //ignore the case insensitive, just to emphasize the example 

и, конечно же, в конце концов найти переливных во всех вариациях с повторением.

Я смог заставить его работать с 1 (единственным) отсутствующим персонажем. Однако, когда я помещаю 2 недостающих символа в свой код, он, очевидно, повторяет один и тот же символ массива для обоих отсутствующих символов, который является БОЛЬШИМ для повторения, но мне также нужно найти его без повторения, и, возможно, может повторяться или не повторяться. Вот то, что я до сих пор: "!"

var r = new Array("A","B","C","D","E","F","G","H","I","J","K", 
        "L","M","N","O","P","Q","R","S","T","U","V", 
        "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9); 
var missing_string = "he!!ow!r!d"; 
var bt_lng = missing_string.length; 
var bruted=""; 

for (z=0; z<r.length; z++) { 
for(var x=0;x<bt_lng;x++){ 
    for(var y=0;y<r.length;y++){ 
     if(missing_string.charAt(x) == "!"){ 
      bruted += r[z]; 
      break; 
     } 
     else if(missing_string.charAt(x) == r[y]){ 
      bruted += r[y]; 
     } 
    } 
} 
console.log("br: " + bruted); 
bruted=""; 
} 

Это прекрасно работает только с одним: "!"

helloworAd 
helloworBd 
helloworCd 
... 
helloworLd 

Однако с 2 или более, я получаю:

heAAowArAd 
heBBowBrBd 
heCCowCrCd 
... 
heLLowLrLd 

который хорош для части повторения, но мне также нужно проверить все возможные символы массива M в каждом отсутствующем месте символа.

Answer 1

Возможно, следующая функция в чистом javascript - это возможное решение для вас. Он использует Array.prototype.reduce для создания декартового продукта c данного алфавита x, при этом его мощность n зависит от количества восклицательных знаков в вашем слове w.

function combinations(w) { 
    var x = new Array(
      "A","B","C","D","E","F","G","H","I","J","K", 
      "L","M","N","O","P","Q","R","S","T","U","V", 
      "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9 
     ), 
     n = w.match(/\!/g).length, 
     x_n = new Array(), 
     r = new Array(), 
     c = null; 

    for (var i = n; i > 0; i--) { 
     x_n.push(x); 
    } 

    c = x_n.reduce(function(a, b) { 
     var c = []; 
     a.forEach(function(a) { 
      b.forEach(function(b) { 
       c.push(a.concat([b])); 
      }); 
     }); 
     return c; 
    }, [[]]); 

    for (var i = 0, j = 0; i < c.length; i++, j = 0) { 
     r.push(w.replace(/\!/g, function(s, k) { 
      return c[i][j++]; 
     })); 
    } 

    return r; 
} 

Назовите его так: console.log(combinations("ov!rf!ow")) в консоли вашего браузера.