1

我们有：

  • 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;
}
4

2 回答 2

4

Cn是第 n 个加泰罗尼亚语数， ，并给出仅使用C(2n,n)/(n+1)的有效长度字符串的数量。因此，如果我们将 all和into更改为，就会有办法。然后有办法改回，还有办法把剩下的改成。综上所述，有办法。2n()[]{}()Cn1+n2+n3C(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。

于 2013-08-05T13:13:09.617 回答
0

一般来说，无限。但是我假设，您的意思是找到有多少组合提供了有限的字符串长度。为简单起见，我们假设极限是偶数。然后，让我们创建一个初始字符串：

(((...()...))) 长度等于限制。

然后，我们可以用 [] 或 {} 括号切换 () 对的任何实例。但是，如果我们更改左大括号，那么我们应该更改匹配的右大括号。因此，我们只能查看左大括号或成对。对于每个括号对，我们有 4 个选项：

  • 保持不变

  • 将其更改为 []

  • 将其更改为 {}

  • 去掉它

因此，对于 (l/2) 个对象中的每一个，我们选择四个标签中的一个，这给出： 4^(l/2)种可能性。

编辑：这假设只有“同心”括号字符串（彼此包含），正如您在编辑中所建议的那样。然而，直观地说，一个有效的组合也是： ()[]{} - 这个解决方案没有考虑到这一点。

于 2013-08-04T17:24:22.630 回答