몇 개의 유효한 괄호 조합입니까?

Question

우리는이 :

• n1{} 브라켓의 수, () 브래킷의

• n2 번호, [] 브래킷의

• n3 번호,

우리가 가질 수있는이 브래킷 중 얼마나 많은 다른 유효한 조합이 있습니까?

내가 생각하는 것 : 나는

(코드는 일반적인 경우를 위해, 그것은 가능한 최악의 솔루션을 알고, (다음에 오는) 자바의 무력 코드를 작성하고 가능한 모든 조합을 계산하는 우리는 다른 종류의 괄호를 가질 수 있습니다.)

어떤 수학적 접근 방식입니까?

주 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

C

n는 n 번째 카탈루냐어 수 C(2n,n)/(n+1)이다, 단지 ()를 사용 2n 길이의 유효한 문자열의 개수를 제공한다. 따라서 [] 및 {}을 ()으로 변경하면 Cn1+n2+n3 가지가됩니다. 그런 다음 n1()을 {}으로 다시 변경하고 C(n2+n3,n3)을 ()으로 변경하는 방법은 []으로 변경하는 방법은 C(n1+n2+n3,n1)입니다. 모두 함께하면, 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 가지 옵션이 있습니다 :

• 휴가는 []로 변경

• 변화는 {}

• 에

• 변화는 그것을

을 제거

그래서 (l/2) 개 개체 각각에 대해 fo ur 레이블은 다음을 제공합니다. 4^(l/2) 가능성.

편집 : 편집시 제안한대로 "동심"괄호 문자열 (서로 포함되어 있음) 만 사용한다고 가정합니다. 그러나 직관적으로 유효한 조합은 다음과 같습니다.() [] {} -이 솔루션은이를 고려하지 않습니다.