基於預定義模式順序生成字符串

Question

我正在研究一個JavaScript項目，該項目需要能夠遍歷模式的所有可能結果。

例如，我會說一個數字，然後從字符串「qwertyuiop」獨立挑選7個字符。我希望它從0qqqqqq開始，然後前進到0qqqqqqw，然後0qqqqqqe等等。

Answer 1

function numbergenerator(char, leng){ 
var chars=char.split(""); 
counters=[]; 
cpos=0; 
for(i=0;i<leng;i++){ 
counters.push(0); 
} 
function gen(){ 
answer=""; 
for(i=0;i<counters.length;i++){ 
answer+=chars[counters[i]]; 
} 
inc(0); 
function inc(pos){ 
if(pos==leng){ 
console.log("maximum reached..."); 
} 
if(counters[pos]==chars.length){ 
counters[pos]=0; 
inc(pos+1); 
}else{ 
counters[pos]++; 
} 
} 
return answer; 
} 
return gen; 
} 

使用這樣的：

gner=numbergenerator("ab",2); 
while(true){ 
console.log(gner());//aa,ba,ab,bb, maximum reached,maximum reached... 
} 
gner=numbergenerator("quertiuop",7); 
while(true){ 
console.log("0"+gner());//0qqqqqqq ,... 
} 

Answer 2

我在JS做了以前的工作Algorithm for Combinations of given numbers with repetition? C++。雖然原始算法是針對整數數組的，但我們也可以爲字符串實現相同的算法。它使用動態編程方法。即使根據你想要的字符數量會有很大的結果，這個應該儘可能以最快的方式完成這項工作。這裏是n = 3的代碼和輸入字符串"qwerty";而對於n = 7，我們應該期望得到279936個組合的結果數組。我謙卑的AMD CPU垃圾在86921毫秒內完成了這項工作。

function combosOfN(a,n){ 
 
    var res = {}; 
 
    a = a.split(""); 
 
    for(var i = 1; i <= n; i++) res[i] = res[i-1] ? res[i-1].reduce((r,e) => r.concat(a.map(n => { var t = e.slice(0); 
 
                           t.push(n); 
 
                           return t; 
 
                           })),[]) 
 
               : a.map(e => [e]); 
 
    return res[n].map(e => "0"+e.join("")); 
 
} 
 

 
var str = "qwerty", 
 
     n = 3, 
 
    res = []; 
 

 
console.time("test"); 
 
res = combosOfN(str,n); 
 
console.timeEnd("test"); 
 
console.log(res);

至於在所有的動態規劃方法，我們從最小的解決方案，並開始朝着最終結果進展。我們從一個空的散列開始。我們保持的哈希看起來像下面，最後結果是第n項（它應該清楚地說明算法的邏輯）

{ '1': [ [ 'q' ], [ 'w' ], [ 'e' ], [ 'r' ], [ 't' ], [ 'y' ] ], 
    '2': 
    [ [ 'q', 'q' ], 
    [ 'q', 'w' ], 
    [ 'q', 'e' ], 
    [ 'q', 'r' ], 
    [ 'q', 't' ], 
    [ 'q', 'y' ], 
    [ 'w', 'q' ], 
    [ 'w', 'w' ], 
    [ 'w', 'e' ], 
    [ 'w', 'r' ], 
    [ 'w', 't' ], 
    [ 'w', 'y' ], 
    [ 'e', 'q' ], 
    [ 'e', 'w' ], 
    [ 'e', 'e' ], 
    [ 'e', 'r' ], 
    [ 'e', 't' ], 
    [ 'e', 'y' ], 
    [ 'r', 'q' ], 
    [ 'r', 'w' ], 
    [ 'r', 'e' ], 
    [ 'r', 'r' ], 
    [ 'r', 't' ], 
    [ 'r', 'y' ], 
    [ 't', 'q' ], 
    [ 't', 'w' ], 
    [ 't', 'e' ], 
    [ 't', 'r' ], 
    [ 't', 't' ], 
    [ 't', 'y' ], 
    [ 'y', 'q' ], 
    [ 'y', 'w' ], 
    [ 'y', 'e' ], 
    [ 'y', 'r' ], 
    [ 'y', 't' ], 
    [ 'y', 'y' ] ], 
    '3': 
    [ [ 'q', 'q', 'q' ], 
    [ 'q', 'q', 'w' ], 
    [ 'q', 'q', 'e' ], 
    [ 'q', 'q', 'r' ], 
    [ 'q', 'q', 't' ], 
    [ 'q', 'q', 'y' ], 
    [ 'q', 'w', 'q' ], 
    [ 'q', 'w', 'w' ], 
    [ 'q', 'w', 'e' ], 
    [ 'q', 'w', 'r' ], 
    [ 'q', 'w', 't' ], 
    [ 'q', 'w', 'y' ], 
    [ 'q', 'e', 'q' ], 
    [ 'q', 'e', 'w' ], 
    [ 'q', 'e', 'e' ], 
    [ 'q', 'e', 'r' ], 
    [ 'q', 'e', 't' ], 
    [ 'q', 'e', 'y' ], 
    [ 'q', 'r', 'q' ], 
    [ 'q', 'r', 'w' ], 
    [ 'q', 'r', 'e' ], 
    [ 'q', 'r', 'r' ], 
    [ 'q', 'r', 't' ], 
    [ 'q', 'r', 'y' ], 
    [ 'q', 't', 'q' ], 
    [ 'q', 't', 'w' ], 
    [ 'q', 't', 'e' ], 
    [ 'q', 't', 'r' ], 
    [ 'q', 't', 't' ], 
    [ 'q', 't', 'y' ], 
    [ 'q', 'y', 'q' ], 
    [ 'q', 'y', 'w' ], 
    [ 'q', 'y', 'e' ], 
    [ 'q', 'y', 'r' ], 
    [ 'q', 'y', 't' ], 
    [ 'q', 'y', 'y' ], 
    [ 'w', 'q', 'q' ], 
    [ 'w', 'q', 'w' ], 
    [ 'w', 'q', 'e' ], 
    [ 'w', 'q', 'r' ], 
    [ 'w', 'q', 't' ], 
    [ 'w', 'q', 'y' ], 
    [ 'w', 'w', 'q' ], 
    [ 'w', 'w', 'w' ], 
    [ 'w', 'w', 'e' ], 
    [ 'w', 'w', 'r' ], 
    [ 'w', 'w', 't' ], 
    [ 'w', 'w', 'y' ], 
    [ 'w', 'e', 'q' ], 
    [ 'w', 'e', 'w' ], 
    [ 'w', 'e', 'e' ], 
    [ 'w', 'e', 'r' ], 
    [ 'w', 'e', 't' ], 
    [ 'w', 'e', 'y' ], 
    [ 'w', 'r', 'q' ], 
    [ 'w', 'r', 'w' ], 
    [ 'w', 'r', 'e' ], 
    [ 'w', 'r', 'r' ], 
    [ 'w', 'r', 't' ], 
    [ 'w', 'r', 'y' ], 
    [ 'w', 't', 'q' ], 
    [ 'w', 't', 'w' ], 
    [ 'w', 't', 'e' ], 
    [ 'w', 't', 'r' ], 
    [ 'w', 't', 't' ], 
    [ 'w', 't', 'y' ], 
    [ 'w', 'y', 'q' ], 
    [ 'w', 'y', 'w' ], 
    [ 'w', 'y', 'e' ], 
    [ 'w', 'y', 'r' ], 
    [ 'w', 'y', 't' ], 
    [ 'w', 'y', 'y' ], 
    [ 'e', 'q', 'q' ], 
    [ 'e', 'q', 'w' ], 
    [ 'e', 'q', 'e' ], 
    [ 'e', 'q', 'r' ], 
    [ 'e', 'q', 't' ], 
    [ 'e', 'q', 'y' ], 
    [ 'e', 'w', 'q' ], 
    [ 'e', 'w', 'w' ], 
    [ 'e', 'w', 'e' ], 
    [ 'e', 'w', 'r' ], 
    [ 'e', 'w', 't' ], 
    [ 'e', 'w', 'y' ], 
    [ 'e', 'e', 'q' ], 
    [ 'e', 'e', 'w' ], 
    [ 'e', 'e', 'e' ], 
    [ 'e', 'e', 'r' ], 
    [ 'e', 'e', 't' ], 
    [ 'e', 'e', 'y' ], 
    [ 'e', 'r', 'q' ], 
    [ 'e', 'r', 'w' ], 
    [ 'e', 'r', 'e' ], 
    [ 'e', 'r', 'r' ], 
    [ 'e', 'r', 't' ], 
    [ 'e', 'r', 'y' ], 
    [ 'e', 't', 'q' ], 
    [ 'e', 't', 'w' ], 
    [ 'e', 't', 'e' ], 
    [ 'e', 't', 'r' ], 
    [ 'e', 't', 't' ], 
    [ 'e', 't', 'y' ], 
    [ 'e', 'y', 'q' ], 
    [ 'e', 'y', 'w' ], 
    [ 'e', 'y', 'e' ], 
    [ 'e', 'y', 'r' ], 
    [ 'e', 'y', 't' ], 
    [ 'e', 'y', 'y' ], 
    [ 'r', 'q', 'q' ], 
    [ 'r', 'q', 'w' ], 
    [ 'r', 'q', 'e' ], 
    [ 'r', 'q', 'r' ], 
    [ 'r', 'q', 't' ], 
    [ 'r', 'q', 'y' ], 
    [ 'r', 'w', 'q' ], 
    [ 'r', 'w', 'w' ], 
    [ 'r', 'w', 'e' ], 
    [ 'r', 'w', 'r' ], 
    [ 'r', 'w', 't' ], 
    [ 'r', 'w', 'y' ], 
    [ 'r', 'e', 'q' ], 
    [ 'r', 'e', 'w' ], 
    [ 'r', 'e', 'e' ], 
    [ 'r', 'e', 'r' ], 
    [ 'r', 'e', 't' ], 
    [ 'r', 'e', 'y' ], 
    [ 'r', 'r', 'q' ], 
    [ 'r', 'r', 'w' ], 
    [ 'r', 'r', 'e' ], 
    [ 'r', 'r', 'r' ], 
    [ 'r', 'r', 't' ], 
    [ 'r', 'r', 'y' ], 
    [ 'r', 't', 'q' ], 
    [ 'r', 't', 'w' ], 
    [ 'r', 't', 'e' ], 
    [ 'r', 't', 'r' ], 
    [ 'r', 't', 't' ], 
    [ 'r', 't', 'y' ], 
    [ 'r', 'y', 'q' ], 
    [ 'r', 'y', 'w' ], 
    [ 'r', 'y', 'e' ], 
    [ 'r', 'y', 'r' ], 
    [ 'r', 'y', 't' ], 
    [ 'r', 'y', 'y' ], 
    [ 't', 'q', 'q' ], 
    [ 't', 'q', 'w' ], 
    [ 't', 'q', 'e' ], 
    [ 't', 'q', 'r' ], 
    [ 't', 'q', 't' ], 
    [ 't', 'q', 'y' ], 
    [ 't', 'w', 'q' ], 
    [ 't', 'w', 'w' ], 
    [ 't', 'w', 'e' ], 
    [ 't', 'w', 'r' ], 
    [ 't', 'w', 't' ], 
    [ 't', 'w', 'y' ], 
    [ 't', 'e', 'q' ], 
    [ 't', 'e', 'w' ], 
    [ 't', 'e', 'e' ], 
    [ 't', 'e', 'r' ], 
    [ 't', 'e', 't' ], 
    [ 't', 'e', 'y' ], 
    [ 't', 'r', 'q' ], 
    [ 't', 'r', 'w' ], 
    [ 't', 'r', 'e' ], 
    [ 't', 'r', 'r' ], 
    [ 't', 'r', 't' ], 
    [ 't', 'r', 'y' ], 
    [ 't', 't', 'q' ], 
    [ 't', 't', 'w' ], 
    [ 't', 't', 'e' ], 
    [ 't', 't', 'r' ], 
    [ 't', 't', 't' ], 
    [ 't', 't', 'y' ], 
    [ 't', 'y', 'q' ], 
    [ 't', 'y', 'w' ], 
    [ 't', 'y', 'e' ], 
    [ 't', 'y', 'r' ], 
    [ 't', 'y', 't' ], 
    [ 't', 'y', 'y' ], 
    [ 'y', 'q', 'q' ], 
    [ 'y', 'q', 'w' ], 
    [ 'y', 'q', 'e' ], 
    [ 'y', 'q', 'r' ], 
    [ 'y', 'q', 't' ], 
    [ 'y', 'q', 'y' ], 
    [ 'y', 'w', 'q' ], 
    [ 'y', 'w', 'w' ], 
    [ 'y', 'w', 'e' ], 
    [ 'y', 'w', 'r' ], 
    [ 'y', 'w', 't' ], 
    [ 'y', 'w', 'y' ], 
    [ 'y', 'e', 'q' ], 
    [ 'y', 'e', 'w' ], 
    [ 'y', 'e', 'e' ], 
    [ 'y', 'e', 'r' ], 
    [ 'y', 'e', 't' ], 
    [ 'y', 'e', 'y' ], 
    [ 'y', 'r', 'q' ], 
    [ 'y', 'r', 'w' ], 
    [ 'y', 'r', 'e' ], 
    [ 'y', 'r', 'r' ], 
    [ 'y', 'r', 't' ], 
    [ 'y', 'r', 'y' ], 
    [ 'y', 't', 'q' ], 
    [ 'y', 't', 'w' ], 
    [ 'y', 't', 'e' ], 
    [ 'y', 't', 'r' ], 
    [ 'y', 't', 't' ], 
    [ 'y', 't', 'y' ], 
    [ 'y', 'y', 'q' ], 
    [ 'y', 'y', 'w' ], 
    [ 'y', 'y', 'e' ], 
    [ 'y', 'y', 'r' ], 
    [ 'y', 'y', 't' ], 
    [ 'y', 'y', 'y' ] ] }