n組のかっこのすべての有効な組み合わせを出力するアルゴリズム

Question

質問文に記載されている問題を処理中です。私は私の解決策が正しいことを知っています（プログラムを実行しました）が、私は私のコード（以下）を正しく分析しているかどうか不思議です。 N すべてのF（n）の値をfとほぼ3倍の数の要素である（：

def parens(num) 
    return ["()"] if num == 1 
    paren_arr = [] 
    parens(num-1).each do |paren| 
    paren_arr << paren + "()" unless "()#{paren}" == "#{paren}()" 
    paren_arr << "()#{paren}" 
    paren_arr << "(#{paren})" 
    end 
    paren_arr 
end 

括弧（3）、一例として、出力は次のようになります。

["()()()", "(()())", "(())()", "()(())", "((()))"] 

ここに私の分析です-1）。したがって、f（n）= 3 * f（n-1）= 3 * 3 * f（n-2）〜（3^n）時間コスト。 同様の分析によって、スタックはf（1）.. f（n）によって占有されるため、空間の複雑さは3^nでなければなりません。

この分析が時間的にも空間的にも正確かどうかはわかりません。一方で、スタックはn個の関数呼び出ししか保持しませんが、これらの呼び出しのそれぞれは、その前の呼び出しの3倍の大きさの配列を返します。スペースコストの要因ですか？私の時間分析は正しいのですか？

Answer 1

私はTom Davisのarticle「Catalan Numbers」がCatalan Numbersを定義するための1つの再帰的方法を説明するのに非常に役立つことを発見しました。 Nの一致する括弧（例えば、1（）; 2（））のすべてのユニークな配列の集合を見つけるのに適用できるので、私はそれを自分自身で説明しようとするでしょう（私は理解しました。 （）、（（））など）。 N > 1について

は(A)BがAとB各括弧の唯一バランスセットを持つN一致括弧の一の構成を表してみましょう。 Aにkの一致するセットが含まれている場合、BはN - k - 1（0 <= k <= N - 1）のいずれかになります。 C_2を列挙するに

C_0 => . 

C_1 => (.) 

、我々はすべての方法でABとしてC_1を手配し、Aの周りに二かっこを配置します：次の例では

、ドットグループは、括弧のゼロセットを有することを意味する

.() = AB = C_0C_1 => (.)() 

() . = AB = C_1C_0 => (()) . 

C_3の場合、それぞれが独自の組み合わせを持つN - 1の3つのパーティションがあります。C_0C_2, C_1C_1, C_2C_0

C_0C_2 = AB = .()() and . (()) =>()()(),()(()) 
C_1C_1 = AB =()()    => (())() 
C_2C_0 = AB =()() . and (()) . => (()()), ((())) 

Nの各セットを保持し、各パーティションの組み合わせを反復することで、この方法をコーディングできます。個々のアレンジをビットとして保持します：左は0、右は1です（これはバイナリ文字列としてキャストされたときに後方に表示されます）。

def catalan 
    Enumerator.new do |y| 
    # the zero here represents none rather than left 
    s = [[0],[2]] 
    y << [0] 
    y << [2] 
    i = 2 

    while true 
     s[i] = [] 

     (0..i - 1).each do |k| 
     as = s[k] 
     bs = s[i - k - 1] 

     as.each do |a| 
      bs.each do |b| 
      if a != 0 
       s[i] << ((b << (2*k + 2)) | (1 << (2*k + 1)) | (a << 1)) 
      else 
       s[i] << (2 | (b << 2)) 
      end 

      end # bs 
     end # as 

     end # k 

     y.yield(s[i]) 

     i = i + 1 
    end # i 

    end # enumerator 
end 

catalan.take(4) 
# => [[0], [2], [10, 12], [42, 50, 44, 52, 56]] 

yielderは怠惰です：

catalan.take(4).last.map{|x| x.to_s(2)} 
# => ["101010", "110010", "101100", "110100", "111000"] 

旧世代は、以前のすべてを保つために私たちを義務づける：リストは無限ですが、我々は我々が（例えば.takeを使用して）好きなように少しを生成することができます次のものを発行するために設定します。あるいは、よりオーガニックなタイプの蛇行再帰によって要求セットを構築することもできます。この次のバージョンでは、ブロックにそれぞれ配置を生み出すので、私たちは入力できます

catalan(4){ 
    |x| (0..7).reduce(""){ 
    |y,i| if x[i] == 0 then y + "(" else y + ")" end 
    } 
}.take(14) 

# => ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", 
#  "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", 
#  "()()(())", "()()()()"] 

を直接世代：

def catalan(n) 
    Enumerator.new do |y| 
    s = [[0,0,0]] 

    until s.empty? 
     left,right,result = s.pop 

     if left + right == 2 * n 
     y << yield(result) 
     end 

     if right < left 
     s << [left, right + 1, result | 1 << (left + right)] 
     end 

     if left < n 
     s << [left + 1, right, result] 
     end 
    end 

    end 
end 

Answer 2

他の人が述べたように、あなたのソリューションが正しくありません。

この問題に対する私のお気に入りの解決方法は、現在の文字列を字句的に次に有効な組み合わせに繰り返し増やして、すべての有効な組み合わせを生成します。

「字句の次は」それはかなり簡単にいくつかのルールに分解：文字列の

• 第1の相違点は、「（」に「）」に変更します。それ以外の場合、次の文字列は現在の文字列の前に字句的に存在します。

• 最初の違いはできるだけ正しいものです。さもなければ、より小さい増分があります。

• 最初の違いの後の部分は字句的に最小ですが、そうでなければ小さいインクリメントがあるからです。この場合、それはすべての '（すべてが'の前に来る '）ことを意味します。

だから、あなたがしなければならないすべては、「（」それに変更することができます「）」右端のを見つけ、それを反転した後、「（」sおよび「）」の正しい番号を追加秒です。

私は、Rubyを知らないが、Pythonで、それは次のようになります。

current="(((())))" 
while True: 
    print(current) 
    opens=0 
    closes=0 
    pos=0 
    for i in range(len(current)-1,-1,-1): 
     if current[i]==')': 
      closes+=1 
     else: 
      opens+=1 
      if closes > opens: 
       pos=i 
       break 
    if pos<1: 
     break 
    current = current[:pos]+ ")" + "("*opens + ")"*(closes-1) 

出力：このような

(((()))) 
((()())) 
((())()) 
((()))() 
(()(())) 
(()()()) 
(()())() 
(())(()) 
(())()() 
()((())) 
()(()()) 
()(())() 
()()(()) 
()()()() 

ソリューションは、多くの種類のための簡単かつ高速であることが判明」すべての組み合わせ "問題を生成する。

Answer 3

再帰的推論は簡単な解決方法です。放して残っている左の括約筋の数が陽性であれば、1つを放出して再発する。放出するために残っている右の括約筋の数が左の数よりも大きい場合、放出し、再発する。ベースケースは、左右のすべての括弧が放射されたときです。印刷します。

def parens(l, r = l, s = "") 
    if l > 0 then parens(l - 1, r, s + "(") end 
    if r > l then parens(l, r - 1, s + ")") end 
    if l + r == 0 then print "#{s}\n" end 
end 

カタロニア語の数字は、印刷される文字列の数を示しています。

このRubyの実装では実現できませんが、Cのような低レベルの言語では、単一の文字列バッファ：O（n）のスペースを簡単に使用できます。サブストリングコピーのため、これはO（n^2）です。しかし、実行時間と出力の長さはO（n！）なので、O（n）スペースの非効率性はあまり意味がありません。