有多少個有效的括號組合？

Question

我們：

• n1的{}括號中的數字，

• n2數量()支架，

• n3一些[]支架，

這些括號有多少種不同的有效組合？

我想什麼：我寫在Java中的蠻力代碼（來自於以下），並計算所有可能的組合，我知道這是最壞的解決方案成爲可能，

（代碼是一般情況，其中我們可以有不同類型的括號）

任何數學方法？

注1：有效組合定義如常，例如， {{()}}：有效，{(}){}：無效

注2：假設我們有2對{}，1雙()和1對的[]，有效組合的數量將是168和所有可能的數量（有效&無效）組合將是840

static void paranthesis_combination(char[] open , char[] close , int[] arr){ 
    int l = 0; 
    for (int i = 0 ; i < arr.length ; i++) 
     l += arr[i]; 
    l *= 2; 
    paranthesis_combination_sub(open , close , arr , new int[arr.length] , new int[arr.length], new StringBuilder(), l); 
    System.out.println(paran_count + " : " + valid_paran_count); 
    return; 
} 


static void paranthesis_combination_sub(char[] open , char[] close, int[] arr , int[] open_so_far , int[] close_so_far, StringBuilder strbld , int l){ 
    if (strbld.length() == l && valid_paran(open , close , strbld)){ 
     System.out.println(new String(strbld)); 
     valid_paran_count++; 
     return; 
    } 
    for (int i = 0 ; i < open.length ; i++){ 
     if (open_so_far[i] < arr[i]){ 
      strbld.append(open[i]); 
      open_so_far[i]++; 
      paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l); 
      open_so_far[i]--; 
      strbld.deleteCharAt(strbld.length() -1); 
     } 
    } 
    for (int i = 0 ; i < open.length ; i++){ 
     if (close_so_far[i] < open_so_far[i]){ 
      strbld.append(close[i]); 
      close_so_far[i]++; 
      paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l); 
      close_so_far[i]--; 
      strbld.deleteCharAt(strbld.length() -1); 
     } 
    } 
    return; 
} 

Answer 1

Cn是第n個Catalan數，C(2n,n)/(n+1)，並給出了僅使用()長度2n的有效弦數。因此，如果我們將所有[]和{}更改爲()，則會有Cn1+n2+n3方式。然後有C(n1+n2+n3,n1)方法將n1()回到{}和C(n2+n3,n3)方法將其餘的()更改爲[]。把這一切放在一起，有C(2n1+2n2+2n3,n1+n2+n3)C(n1+n2+n3,n1)C(n2+n3,n3)/(n1+n2+n3+1)方式。

作爲支票，當n1=2，n2=n3=1，我們有C(8,4)C(4,2)C(2,1)/5=168。

Answer 2

一般來說，無限。不過，我認爲，你的意思是找出有多少組合提供了有限的字符串長度。爲了簡單起見，我們假設極限是偶數。然後，讓我們創建一個初始字符串：

（（（...（）...））），長度等於極限。

然後，我們可以用[]或{}圓括號切換（）對的任何實例。但是，如果我們更改了大括號，那麼我們應該更改匹配的大括號。所以，我們只能看到開頭的大括號，或者成對的。對於每個括號對我們有4個選項：

• 假它不變

• 它變化到[]

• 它變化爲{}

• 刪除它

因此，對於每個（1/2）對象，我們選擇一個fo這些標籤給出了： 4 ^（1/2）的可能性。

編輯：這裏假定只有「同心」括號字符串（包含在對方中），正如您在編輯中所建議的那樣。直觀地說，一個有效的組合也是：（）[] {} - 這個解決方案沒有考慮到這一點。