JavaScriptで単語内の文字置換のすべての可能な組み合わせを生成するにはどうすればよいですか？

Question

「zazaza」という言葉を考えてみましょう。

私は、置き換える文字とその文字と一致する単語が与えられ、その文字置換のすべての組み合わせを生成する関数を考え出しています。

私はこのように、一致する文字と置き換えるための文字が含まれているJSONを持っています。このようなものになるだろう

var replacement = {original: 'Z', replace: 'S'};

フル例：

そして、配列には以下が含まれます：

zazaza 
sazaza 
sasaza 
sasasa 
zasasa 
zazasa 
... 

eは再帰で実装する方が簡単ですが、JavaScriptの関数呼び出しは高価になる可能性があるので、私が理解しているように、そのアプローチをとることについてはわかりません。私の主な問題は、私がすべての組み合わせを生成していることを保証する方法だと思います。

この配列を作成する目的は、これらのすべての単語を別のものと照合することができるためです。これを実行できる正規表現が実装されているかどうかわかりません。

Answer 1

置換文字を挿入するN個の可能な位置があり、あなたの仕事は、一連の位置のすべての可能なサブセットを生成することに至ります。これは、各反復がループカウンタのセットビットに対応する要素を含むサブセットを放出する、0から2^Nまで反復することによって行うことができる。

これは非常に効率的ですが、javascriptの制限のため最大32個の要素に対してのみ動作します。一般的なケースでは

、再帰は例えば、移動するための方法である：

let powerset = a => _powerset([[]], a); 

let _powerset = (out, rest) => 
    rest.length ? 
     _powerset(
      out.concat(out.map(x => x.concat(rest[0]))), 
      rest.slice(1)) 
     : out; 

注意この関数は末尾再帰であるので、現代のJSエンジンは、関数が離れて呼び出しを最適化できるようになること。

（退屈コンパイルするV8を待っているので、ここで完全なコードだ）;）

let powerset = a => _powerset([[]], a); 
 

 
let _powerset = (out, rest) => 
 
    rest.length ? 
 
     _powerset(
 
      out.concat(out.map(x => x.concat(rest[0]))), 
 
      rest.slice(1)) 
 
     : out; 
 

 
let enumerate = (str, char) => [...str] 
 
    .map((c, i) => [c, i]) 
 
    .filter(p => p[0] === char) 
 
    .map(p => p[1]); 
 

 
let translate = (str, pos, replace) => [...str] 
 
    .map((c, i) => pos.includes(i) ? replace : c) // @todo: optimize me 
 
    .join(''); 
 

 

 
let allReplacements = (str, char, replace) => 
 
    powerset(enumerate(str, char)).map(pos => translate(str, pos, replace)); 
 

 

 
console.log(allReplacements('_abc_def_x', '_', '@'));