找到格式正确的括号的所有组合

Question

这是在与朋友交谈时提出的,我想我会问这里,因为这是一个有趣的问题,并希望看到其他人的解决方案.

任务是编写一个函数Brackets(int n),它打印1 ... n 中格式正确的括号的所有组合.对于Brackets(3),输出将是

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

Answer 1

抓住了它...... 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);
    }
}

递归利用了这样一个事实,即你永远不能添加比所需数量的对更多的开括号,并且你永远不能添加更多的结束括号而不是开括号.

Answer 2

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")

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

Answer 3

可能组合的数量是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);

输出:
()
(())()()
((()))(()())(())()()(())()()()

Answer 4

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)

Answer 5

这是另一个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,但它很容易把它包起来.