文字列が与えられた場合、各部分文字列がN個以下でM個以下の文字を含む可能性のある部分文字列のすべての可能な配列を生成する方法はありますか？

Question

私は文字列strと2つの正の整数MとNを持っています。ここでMはN以下です。私が望むのは、文字列を分割して、各部分が文字以下で、M文字以上であることです（文字列の長さがMより大きいと仮定します）。Nより大きくない場合、 Nは文字列の長さに等しい）。例えば、M=1、N=3と私の文字列が"aabcde"であれば、結果は

var str = "aabcde"; 
var result = [ 
["a", "a", "b", "cde"], 
["a", "ab", "cde"], 
["aa", "b", "cde"], 
//... 
["aab", "cde"], 
["aab", "cd", "e"], 
["aab", "c", "de"], 
["aab", "c", "d", "e"] 
] 

である必要があり、不要な中間サブアレイを避けて、この問題を解決するための効率的な方法は何ですか？私はすべての可能な組み合わせを生成し、許容されない長さの部分文字列が少なくとも1つ含まれている場合は、各部分配列を削除したくありません。不要な計算をすることなく別の方法がありますか？

Answer 1

これは効果的に二つの値MとN間の部分とinteger compositions制限発生に帰着。そのような構成を再帰的に生成することは簡単な問題である。

"aabcde", M=1, N=3"の例では、配列の長さがすべて4以下であることに気がついたので、オプションのパラメータを使用して各コンポジションの部品数を制限しました。

function* restrictedCompositions(n, a, b, k = n) { 
    if (!(0 < a && a <= b && b <= n && 0 < k && k <= n)) { 
     throw "invalid arguments"; 
    } 

    let C = []; 

    function* recGen(m, r) { 
     if (m == 0) { 
      yield C; // client must copy if they wish to store value for later 
     } 
     else { 
      let y = Math.min(b, m); 
      let x = Math.max(a, m - y*(r - 1)); 

      for (let v = x; v <= y; v++) { 
       C.push(v); 
       yield* recGen(m - v, r - 1); 
       C.pop(); 
      } 
     } 
    } 

    yield* recGen(n, k); 
} 

function* generateChoppedStrings(str, M, N, K = str.length) { 
    for (let composition of restrictedCompositions(str.length, M, N, K)) { 
     let chopped = []; 
     let i = 0; 

     for (let part of composition) { 
      let j = i + part; 
      chopped.push(str.slice(i, j)); 
      i = j; 
     } 

     yield chopped; 
    } 
} 

function chopString(str, M, N, K = str.length) { 
    for (let chopped of generateChoppedStrings(str, M, N, K)) { 
     console.log(chopped); 
    } 
} 

chopString("aabcde", 1, 3, 4); 

出力：

Answer 2

再帰を使用してすべての可能な配列を生成できます。可能なすべての開始部分文字列（長さM..N）を取得し、残りの文字列の次の再帰レベルを呼び出します。

このアプローチは、過剰な（悪い）サブアレイを生成しません（ただし、文字列の末尾からいくつかの時間を同じセットを生成することができます）

あなたがストリングで、かつ分割位置の整数配列の両方で動作することに注意してください、と再帰の最後のステップで実際の部分文字列を作る。

単純デルファイ例：

procedure SplitStr(s, Reslt: string; LMin, LMax: Integer); 
var 
    i, Len: Integer; 
    left, right: string; 
begin 
    Len := Length(s); 
    if Len = 0 then 
    Memo1.Lines.Add(Reslt) 
    else 
    for i := LMin to Min(LMax, Len) do begin 
     left := LeftStr(s, i); 
     right := RightStr(s, Len - i); 
     SplitStr(right, Reslt + left + '| ' , LMin, LMax); 
    end; 
end; 

begin 
    SplitStr('aabcde', '', 1, 3); 

出力

a| a| b| c| d| e| 
a| a| b| c| de| 
a| a| b| cd| e| 
a| a| b| cde| 
a| a| bc| d| e| 
a| a| bc| de| 
a| a| bcd| e| 
a| ab| c| d| e| 
a| ab| c| de| 
a| ab| cd| e| 
a| ab| cde| 
a| abc| d| e| 
a| abc| de| 
aa| b| c| d| e| 
aa| b| c| de| 
aa| b| cd| e| 
aa| b| cde| 
aa| bc| d| e| 
aa| bc| de| 
aa| bcd| e| 
aab| c| d| e| 
aab| c| de| 
aab| cd| e| 
aab| cde|