C# 查找格式正确的括号的所有组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/727707/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding all combinations of well-formed brackets
提问by aleemb
This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions.
这是在与朋友交谈时出现的，我想我会在这里问，因为这是一个有趣的问题，并且希望看到其他人的解决方案。
The task is to write a function Brackets(int n) that prints all combinations of well-formedbrackets from 1...n. For Brackets(3) the output would be
任务是编写一个函数 Brackets(int n)，该函数打印1...n中格式正确的括号的所有组合。对于 Brackets(3) 输出将是
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
采纳答案by markt
Took a crack at it.. C# also.
尝试了一下.. 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);
}
}
The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..
递归利用这样一个事实，即您永远不能添加比所需对数更多的左括号，并且您永远不能添加比左括号更多的右括号。
回答by Brian
F#:
F#：
UPDATE: this answer is wrong. My N=4 misses, for example "(())(())". (Do you see why?) I will post a correct (and more efficient) algorithm shortly.
更新：这个答案是错误的。我的 N=4 未命中，例如“(())(())”。（你明白为什么吗？）我将很快发布一个正确（并且更有效）的算法。
(Shame on all you up-voters, for not catching me! :) )
（为你们所有的投票者感到羞耻，因为没有抓住我！:)）
Inefficient, but short and simple. (Note that it only prints the 'nth' line; call in a loop from 1..n to get the output asked for by the question.)
效率低下，但简短而简单。（请注意，它只打印 'nth' 行；从 1..n 循环调用以获取问题要求的输出。）
#light
let rec brackets n =
if n = 1 then
["()"]
else
[for s in brackets (n-1) do
yield "()" ^ s
yield "(" ^ s ^ ")"
yield s ^ "()"]
Example:
例子：
Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
回答by Brian
F#:
F#：
Here is a solution that, unlike my previous solution, I believe may be correct. Also, it is more efficient.
这是一个解决方案，与我之前的解决方案不同，我认为它可能是正确的。此外，它更有效。
#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
Example:
例子：
(brackets2 4) |> Seq.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
回答by KingNestor
The number of possible combinations is the Catalan numberof N pairs C(n).
This problem was discussed on the joelonsoftware.com forumspretty exentsively including iterative, recursive and iterative/bitshifting solutions. Some pretty cool stuff there.
这个问题在 joelonsoftware.com 论坛上进行了相当广泛的讨论，包括迭代、递归和迭代/位移解决方案。那里有一些很酷的东西。
Here is a quick recursive solution suggested on the forums in C#:
这是在 C# 论坛上建议的快速递归解决方案：
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;
}
Brackets(3);
括号(3);
Output:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
输出：
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
回答by Bobby Hyman
Damn - everyone beat me to it, but I have a nice working example :)
该死 - 每个人都打败了我，但我有一个很好的工作示例:)
http://www.fiveminuteargument.com/so-727707
http://www.fiveminuteargument.com/so-727707
The key is identifying the rules, which are actually quite simple:
关键是识别规则，其实很简单：
- Build the string char-by-char
- At a given point in the string
- if brackets in string so far balance (includes empty str), add an open bracket and recurse
- if all open brackets have been used, add a close bracket and recurse
- otherwise, recurse twice, once for each type of bracket
- Stop when you get to the end :-)
- 逐字符构建字符串
- 在字符串中的给定点
- 如果到目前为止字符串中的括号平衡（包括空 str），则添加一个左括号并递归
- 如果使用了所有左括号，则添加右括号并递归
- 否则，递归两次，每种类型的括号一次
- 走到最后就停下来:-)
回答by MahlerFive
Here is a solution in C++. The main idea that I use is that I take the output from the previous i(where iis the number of bracket pairs), and feed that as input to the next i. Then, for each string in the input, we put a bracket pair at each location in the string. New strings are added to a set in order to eliminate duplicates.
这是 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;
}
回答by kvb
Here's another F# solution, favoring elegance over efficiency, although memoization would probably lead to a relatively well performing variant.
这是另一个 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]
Again, this only yields a list of those strings with exactlyn pairs of parens (rather than at most n), but it's easy to wrap it.
同样，这只会产生一个包含恰好n 对括号（而不是最多 n）的字符串列表，但很容易包装它。
回答by Pete Kirkham
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, which is something like an actor model based linear python with traits. I haven't got round to implementing @memo but the above works without that optimisation)
（kin，这有点像基于演员模型的带有特征的线性python。我还没有开始实施@memo，但上述工作没有经过优化）
回答by Raoul Supercopter
A simple F#/OCaml solution :
一个简单的 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)
回答by Sebastian Krog
Common Lisp:
通用 Lisp：
This doesn't print them, but does produce a list of lists of all the possible structures. My method is a bit different from the others'. It restructures the solutions to brackets(n - 1)such that they become brackets(n). My solution isn't tail recursive, but it could be made so with a little work.
这不会打印它们，但会生成所有可能结构的列表。我的方法和别人的有点不同。它重新构造解决方案，以brackets(n - 1)使它们成为这样brackets(n)。我的解决方案不是尾递归的，但可以通过一些工作来实现。
Code
代码
(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))))
