c# - 整形式のブラケットのすべての組み合わせを見つける

Question

これは友人と話しているときに出てきたもので、興味深い問題であり、他の人の解決策を見たいので、ここで質問しようと思いました.

タスクは、1...nの整形式ブラケットのすべての組み合わせを出力する関数 Brackets(int n) を作成することです。Brackets(3) の場合、出力は次のようになります。

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

score 54 · Accepted Answer

それにクラックを取った.. C#も。

public void Brackets(int n) {
    for (int i = 1; i <= n; i++) {
        Brackets("", 0, 0, i);
    }
}

private void Brackets(string output, int open, int close, int pairs) {
    if((open==pairs)&&(close==pairs)) {
        Console.WriteLine(output);
    } else {
        if(open<pairs)
            Brackets(output + "(", open+1, close, pairs);
        if(close<open)
            Brackets(output + ")", open, close+1, pairs);
    }
}

再帰は、必要な数のペアよりも多くの開き括弧を追加することはできず、開き括弧よりも多くの閉じ括弧を追加することはできないという事実を利用しています..

score 10 · Accepted Answer

最初に投票された回答の Python バージョン。

def foo(output, open, close, pairs):
    if open == pairs and close == pairs:
        print output
    else:
        if open<pairs:
            foo(output+'(', open+1, close, pairs)
        if close<open:
            foo(output+')', open, close+1, pairs)

foo('', 0, 0, 3)

score 9 · Accepted Answer

F＃：

これが私の以前の解決策とは異なり、正しいかもしれないと私が信じている解決策です。また、より効率的です。

#light

let brackets2 n =
    let result = new System.Collections.Generic.List<_>()
    let a = Array.create (n*2) '_'
    let rec helper l r diff i =
        if l=0 && r=0 then
            result.Add(new string(a))
        else
            if l > 0 then
                a.[i] <- '('
                helper (l-1) r (diff+1) (i+1)
            if diff > 0 then
                a.[i] <- ')'
                helper l (r-1) (diff-1) (i+1)
    helper n n 0 0
    result

例：

(brackets2 4) |> Seq.iter (printfn "%s")

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

score 9 · Accepted Answer

可能な組み合わせの数は、NペアC（n）のカタラン数です。

この問題は、joelonsoftware.comフォーラムで、反復、再帰、反復/ビットシフトのソリューションを含めてかなり広範囲に議論されました。そこにいくつかのかなりクールなもの。

C＃のフォーラムで提案されている簡単な再帰的ソリューションは次のとおりです。

C＃

public void Brackets(int pairs) {
    if (pairs > 1) Brackets(pairs - 1);
    char[] output = new char[2 * pairs];

    output[0] = '(';
    output[1] = ')';

    foo(output, 1, pairs - 1, pairs, pairs);
    Console.writeLine();
}

public void foo(char[] output, int index, int open, int close,
        int pairs) {
    int i;

    if (index == 2 * pairs) {
        for (i = 0; i < 2 * pairs; i++)
            Console.write(output[i]);
        Console.write('\n');
        return;
    }

    if (open != 0) {
        output[index] = '(';
        foo(output, index + 1, open - 1, close, pairs);
    }

    if ((close != 0) && (pairs - close + 1 <= pairs - open)) {
        output[index] = ')';
        foo(output, index + 1, open, close - 1, pairs);
    }

    return;
}

ブラケット（3）;

出力:
(）
（（））（）（）
（（（）））（（）（））（（））（）（）（（））（）（）（）

score 5 · Accepted Answer

これは、効率よりも優雅さを優先する別の F# ソリューションですが、メモ化はおそらく比較的パフォーマンスの良いバリアントにつながるでしょう。

let rec parens = function
| 0 -> [""]
| n -> [for k in 0 .. n-1 do
        for p1 in parens k do
        for p2 in parens (n-k-1) ->
          sprintf "(%s)%s" p1 p2]

繰り返しますが、これは (多くとも n ではなく)正確にn ペアの括弧を持つ文字列のリストしか生成しませんが、それをラップするのは簡単です。

score 4 · Accepted Answer

C ++の簡単な解決策：

#include <iostream>
#include <string>

void brackets(string output, int open, int close, int pairs)
{
    if(open == pairs && close == pairs)
            cout << output << endl;
    else
    {
            if(open<pairs)
                    brackets(output+"(",open+1,close,pairs);
            if(close<open)
                    brackets(output+")",open,close+1,pairs);
    }
}

int main()
{
    for(int i=1;i<=3;i++)
    {
            cout << "Combination for i = " << i << endl;
            brackets("",0,0,i);
    }
}

出力：

Combination for i = 1
()
Combination for i = 2
(())
()()
Combination for i = 3
((()))
(()())
(())()
()(())
()()()

score 3 · Accepted Answer

一般的な Lisp:

これはそれらを印刷しませんが、すべての可能な構造のリストのリストを生成します。私の方法は、他の方法とは少し異なります。brackets(n - 1)になるように解を再構築しbrackets(n)ます。私の解決策は末尾再帰ではありませんが、ちょっとした作業でそうすることができます。

コード

(defun brackets (n)
  (if (= 1 n)
      '((()))
      (loop for el in (brackets (1- n))
            when (cdr el)
            collect (cons (list (car el)) (cdr el))
            collect (list el)
            collect (cons '() el))))

score 3 · Accepted Answer

くそー-誰もが私を打ち負かしましたが、私は素晴らしい実用的な例を持っています:)

http://www.fiveminuteargument.com/so-727707

重要なのは、ルールを特定することです。ルールは実際には非常に単純です。

文字列を char-by-char で構築する
文字列の特定のポイントで
- これまでの文字列の括弧のバランスが取れている場合 (空の str を含む)、開き括弧を追加して再帰します
- すべての開き括弧が使用されている場合は、閉じ括弧を追加して再帰します
- それ以外の場合は、ブラケットの種類ごとに 1 回ずつ、2 回再帰します。
最後まで来たらやめてください:-)

score 2 · Accepted Answer

シンプルなF＃/ OCamlソリューション：

let total_bracket n =
    let rec aux acc = function
        | 0, 0 -> print_string (acc ^ "\n")
        | 0, n -> aux (acc ^ ")") (0, n-1)
        | n, 0 -> aux (acc ^ "(") (n-1, 1)
        | n, c ->
                aux (acc ^ "(") (n-1, c+1);
                aux (acc ^ ")") (n,   c-1)
    in
    aux "" (n, 0)

score 2 · Accepted Answer

これがC++での解決策です。私が使用する主なアイデアは、前のiからの出力( iは括弧のペアの数) を取得し、それを次のiへの入力としてフィードすることです。次に、入力の各文字列に対して、文字列の各位置にブラケットペアを配置します。重複を排除するために、新しい文字列がセットに追加されます。

#include <iostream>
#include <set>
using namespace std;
void brackets( int n );
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set );

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    brackets(n);
    return 0;
}

void brackets( int n ) {
    set<string>* set1 = new set<string>;
    set<string>* set2;

    for( int i = 1; i <= n; i++ ) {
        set2 = new set<string>;
        brackets_aux( i, *set1, *set2 );
        delete set1;
        set1 = set2;
    }
}

void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ) {
    // Build set of bracket strings to print
    if( x == 1 ) {
        output_set.insert( "()" );
    }
    else {
        // For each input string, generate the output strings when inserting a bracket pair
        for( set<string>::iterator s = input_set.begin(); s != input_set.end(); s++ ) {
            // For each location in the string, insert bracket pair before location if valid
            for( unsigned int i = 0; i < s->size(); i++ ) {
                string s2 = *s;
                s2.insert( i, "()" );
                output_set.insert( s2 );
            }
            output_set.insert( *s + "()" );
        }
    }

    // Print them
    for( set<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) {
        cout << *i << "  ";
    }
    cout << endl;
}

score 1 · Accepted Answer

なぜこれがこれほど単純なのか、このアイデアは非常に単純です

ブラケット(n) --> '()' + ブラケット(n-1) 0 '(' + ブラケット(n-1) + ')' 0 ブラケット(n-1) + '()'

ここで、0 は上記の連結操作です

public static Set<String> brackets(int n) {
    if(n == 1){
        Set<String> s = new HashSet<String>();
        s.add("()");
        return s;
    }else{
        Set<String> s1 = new HashSet<String>();
        Set<String> s2 = brackets(n - 1);
        for(Iterator<String> it = s2.iterator(); it.hasNext();){
            String s = it.next();
            s1.add("()" + s);
            s1.add("(" + s + ")");
            s1.add(s + "()");
        }
        s2.clear();
        s2 = null;
        return s1;
    }
}

score 1 · Accepted Answer

ハスケル:

私はこれに対するエレガントなリストモナドの方法を考え出そうとしました:

import Control.Applicative

brackets :: Int -> [String]
brackets n = f 0 0 where
    f pos depth =
        if pos < 2*n
            then open <|> close
            else stop where
                -- Add an open bracket if we can
                open =
                    if depth < 2*n - pos
                        then ('(' :) <$> f (pos+1) (depth+1)
                        else empty

                -- Add a closing bracket if we can
                close = 
                    if depth > 0
                        then (')' :) <$> f (pos+1) (depth-1)
                        else empty

                -- Stop adding text.  We have 2*n characters now.
                stop = pure ""

main = readLn >>= putStr . unlines . brackets

score 1 · Accepted Answer

def @memo brackets ( n )
    => [] if n == 0 else around( n ) ++ pre( n ) ++ post( n ) ++ [ "()" * n) ]

def @memo pre ( n )
    => map ( ( s ) => "()" ++ s, pre ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []

def @memo post ( n )
    => map ( ( s ) => s ++ "()", post ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []

def @memo around ( n )
    => map ( ( s ) => "(" ++ s ++ ")", brackets( n - 1 ) )

( kin、これは特性を備えたアクターモデルベースの線形 python のようなものです。@memo を実装するまでには至っていませんが、上記はその最適化なしで機能します)

score 1 · Accepted Answer

上記の markt のエレガントな c# ソリューションに基づく Groovy バージョン。オープンとクローズを動的にチェックし (情報は出力と引数で繰り返されます)、無関係なロジックチェックをいくつか削除しました。

3.times{ 
    println bracks(it + 1)
}

def bracks(pairs, output=""){
    def open = output.count('(')
    def close = output.count(')')

    if (close == pairs) {
        print "$output "
    }
    else {
        if (open < pairs) bracks(pairs, "$output(")
        if (close < open) bracks(pairs, "$output)")
    }
    ""
}

score 0 · Accepted Answer

//C program to print all possible n pairs of balanced parentheses  


#include<stdio.h>

void fn(int p,int n,int o,int c);

void main()
{
    int n;
    printf("\nEnter n:");
    scanf("%d",&n);
    if(n>0)  
        fn(0,n,0,0);
}

void fn(int p,int n,into,int c)
{  
    static char str[100];
    if(c==n)
    {
        printf("%s\n",str);
        return;
    }
    else
    {
        if(o>c)
        {
            str[p]='}';
            fn(p+1,n,o,c+1);
        }
        if(o<n)
        {
            str[p]='{';
            fn(p+1,n;o+1,c);
        }
    }
}

score 0 · Accepted Answer

メモ化の試み:

void push_strings(int i, int j ,vector<vector <string>> &T){
    for (int k=0; k< T[j].size(); ++k){
        for (int l=0; l< T[i - 1 - j].size(); ++l){
            string s = "(" + T[j][k] + ")" + T[i-1 - j][l];
            T[i].push_back(s);
        }
    }
}

vector<string> generateParenthesis(int n) {
    vector<vector <string>> T(n+10);
    T[0] = {""};

    for (int i =1; i <=n; ++i){
        for(int j=0; j<i; ++j){
            push_strings(i,j, T);
        }
    }

    return T[n];
}

score 0 · Accepted Answer

void function(int n, string str, int open, int close)
{
    if(open>n/2 || close>open)
        return;
    if(open==close && open+close == n)
    {
        cout<<" "<<str<<endl;
        return;
    }
    function(n, str+"(", open+1, close);
    function(n, str+")", open, close+1);
}

発信者 - function(2*brackets, str, 0, 0);

score 0 · Accepted Answer

def form_brackets(n: int) -> set:
    combinations = set()
    if n == 1:
        combinations.add('()')
    else:
        previous_sets = form_brackets(n - 1)
        for previous_set in previous_sets:
            for i, c in enumerate(previous_set):
                temp_string = "{}(){}".format(previous_set[:i+1], previous_set[i+1:])
                combinations.add(temp_string)

    return combinations

score 0 · Accepted Answer

別の非効率的だがエレガントな答え =>

public static Set<String> permuteParenthesis1(int num)
{   
    Set<String> result=new HashSet<String>();
    if(num==0)//base case
        {
            result.add("");
            return result;
        }
    else
        {
            Set<String> temp=permuteParenthesis1(num-1); // storing result from previous result.
            for(String str : temp)
            {
                for(int i=0;i<str.length();i++)
                {
                    if(str.charAt(i)=='(')
                    {
                        result.add(insertParen(str, i)); // addinng `()` after every left parenthesis.
                    }
                }
                result.add("()"+str); // adding "()" to the beginning.
            }

        }
    return result;


}
public static String insertParen(String str,int leftindex)
{
    String left=str.substring(0, leftindex+1);
    String right=str.substring(leftindex+1);
    return left+"()"+right;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(permuteParenthesis1(3));

}

score 0 · Accepted Answer

最も洗練されたソリューションではありませんが、これは C++ (Visual Studio 2008) で行った方法です。STL セットを利用して重複を排除し、単純に新しい () ペアを前の世代のすべての文字列の各文字列インデックスに挿入し、再帰します。

#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>

using namespace System;
using namespace std;

typedef set<string> StrSet;

void ExpandSet( StrSet &Results, int Curr, int Max )
{
    if (Curr < Max)
    {
        StrSet NewResults;

        for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
        {
            for (unsigned int stri=0; stri < (*it).length(); stri++)
            {
                string NewStr( *it );
                NewResults.insert( NewStr.insert( stri, string("()") ) );
            }
        }
        ExpandSet( NewResults, Curr+1, Max );

        Results = NewResults;
    }
}    

int main(array<System::String ^> ^args)
{
    int ParenCount = 0;

    cout << "Enter the parens to balance:" << endl;
    cin  >> ParenCount;

    StrSet Results;
    Results.insert( string("()") );

    ExpandSet(Results, 1, ParenCount);

    cout << Results.size() << ": Total # of results for " << ParenCount << " parens:" << endl;

    for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
    {
        cout << *it << endl;
    }


    return 0;
}

score 0 · Accepted Answer

ルビーバージョン:

def foo output, open, close, pairs
  if open == pairs and close == pairs
      p output
  else
    foo(output + '(', open+1, close, pairs) if open < pairs
    foo(output + ')', open, close+1, pairs) if close < open
  end
end
foo('', 0, 0, 3)

score 0 · Accepted Answer

  validParentheses: function validParentheses(n) {
    if(n === 1) {
      return ['()'];
    }
    var prevParentheses = validParentheses(n-1);
    var list = {};
    prevParentheses.forEach(function(item) {
      list['(' + item + ')'] = null;
      list['()' + item] = null;
      list[item + '()'] = null;
    });
    return Object.keys(list);
  }

c# - 整形式のブラケットのすべての組み合わせを見つける

29 に答える 29

C＃

一般的な Lisp:

コード

ハスケル:

Related

Reference