Поиск всех комбинаций правильных скобок
Это возникло во время разговора с другом, и я подумал спросить здесь, потому что это интересная проблема и хотел бы увидеть решения других людей.
Задача состоит в том, чтобы написать функцию Brackets(int n), которая печатает все комбинации правильно сформированных скобок от 1...n. Для скобок (3) вывод будет
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
31 ответ
Взял трещину на это.. 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);
}
}
В рекурсии используется тот факт, что вы никогда не сможете добавить больше открывающих скобок, чем желаемое количество пар, и вы никогда не сможете добавить больше закрывающих скобок, чем открывающих скобок.
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)
Число возможных комбинаций - каталонское число 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);
Выход:
()
(()) () ()
((())) (() ()) (()) () () (()) () () ()
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")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Вот еще одно решение 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), но это легко обернуть.
F#:
ОБНОВЛЕНИЕ: этот ответ неверен. Мой N=4 промахов, например "(())(())". (Вы понимаете, почему?) В скором времени я опубликую правильный (и более эффективный) алгоритм.
(Позор всем вам, избирателям, за то, что не поймали меня!:))
Неэффективно, но коротко и просто. (Обратите внимание, что он печатает только n-ю строку; вызов в цикле из 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 ^ "()"]
Пример:
Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Простое решение в 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
((()))
(()())
(())()
()(())
()()()
Блин - все меня опередили, но у меня есть хороший рабочий пример:)
http://www.fiveminuteargument.com/so-727707
Ключ идентифицирует правила, которые на самом деле довольно просты:
- Построить строку char-by-char
- В данный момент в строке
- если скобки в строке пока сбалансированы (включая пустую строку), добавьте открытую скобку и рекурсив
- если все открытые скобки были использованы, добавьте закрывающую скобку и введите
- в противном случае, повторять дважды, один раз для каждого типа скобок
- Остановись, когда доберешься до конца:-)
Common 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))))
Простое решение 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)
Вот решение в 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;
}
Версия провайдера C#, основанная на рекурсивном алгоритме возврата, надеюсь, это будет полезно.
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<String>();
Generate("", 0, 0, n, result);
return result;
}
private void Generate(String s, int l, int r, int n, List<String> result){
if(l == n && r == n){
result.add(s);
return;
}
if(l<n){
Generate(s+"(", l+1, r, n, result);
}
if(r < l)
Generate(s+")", l , r+1, n, result);
}}
Отличная версия, основанная на элегантном решении C# от Markt выше. Динамическая проверка открытия и закрытия (информация была повторена в выходных данных и аргументах), а также удаление пары посторонних логических проверок.
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)")
}
""
}
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 ) )
( Кин, это что-то вроде линейного питона на основе актерской модели с чертами. Я не дошел до реализации @memo, но вышеописанное работает без этой оптимизации)
Haskell:
Я попытался придумать элегантный список монадой у этого пути:
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
Почему это так просто, эта идея довольно проста
скобки (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;
}
}
Мне задали этот вопрос сегодня в интервью.
Я всегда пропускал этот вопрос в Cracking The Coding, потому что думал, что это глупый вопрос для интервью. Интервьюер не разделял моего мнения.
Ниже приведено решение, которое я мог бы найти в интервью. Интервьюер искал более эффективный метод, который уже был приведен выше. Он передал меня, хотя для этого решения.
//This method is recursive. It simply returns all the possible arrangements by going down
//and building all possible combinations of parenthesis arrangements by starting from "()"
//Using only "()" for n == 1, it puts one "()" before, one "()" after and one "()" around
//each paren string returned from the call stack below. Since, we are adding to a set, the
//set ensure that any combination is not repeated.
private HashSet<string> GetParens(int num)
{
//If num < 1, return null.
if (num < 1) return null;
//If num == 1, there is only valid combination. Return that.
if (num == 1) return new HashSet<string> {"()"};
//Calling myself, by subtracting 1 from the input to get valid combinations for 1 less
//pair.
var parensNumMinusOne = GetParens(num - 1);
//Initializing a set which will hold all the valid paren combinations.
var returnSet = new HashSet<string>();
//Now generating combinations by using all n - 1 valid paren combinations one by one.
foreach (var paren in parensNumMinusOne)
{
//Putting "()" before the valid paren string...
returnSet.Add("()" + paren);
//Putting "()" after the valid paren string...
returnSet.Add(paren + "()");
//Putting paren pair around the valid paren string...
returnSet.Add("(" + paren + ")");
}
return returnSet;
}
Пространственная сложность другого более производительного решения - O(1), но для этого - O (Cn), где Cn - каталонское число.
Временная сложность этого кода такая же, как и у другого высокопроизводительного решения, такого же, как O (Cn).
Попытка с запоминанием:
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];
}
Еще одно решение для решения этой проблемы.
правильная строка: (){}[]
неправильная строка: ([{)]}
private static boolean isEqualBracket(String str) {
Stack stack = new Stack();
if (str != null && str.length() > 0) {
for (int i = 0; i < str.length(); i++) {
char nextChar = str.charAt(i);
if (nextChar == '(' || nextChar == '{' || nextChar == '[') {
stack.push(nextChar);
} else if (nextChar == ')' || nextChar == '}' || nextChar == ']') {
char startChar = stack.peek().toString().charAt(0);
if ((startChar == '(' && nextChar == ')') || (startChar == '{' && nextChar == '}') || (startChar == '[' && nextChar == ']')) {
stack.pop();
} else {
return false;
}
} else {
return false;
}
}
} else {
return false;
}
return stack.empty();
}
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
Еще один неэффективный, но элегантный ответ =>
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));
}
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> combinations = new List<string>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<string> result) {
if (pos == current.Length) {
if (valid(current))
result.Add(new string(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public bool valid(char[] current) {
int balance = 0;
foreach (char c in current) {
if (c == '(')
balance++;
else balance--;
if (balance < 0)
return false;
}
return (balance == 0);
}
}
results = []
num = 0
def print_paratheses(left, right):
global num
global results
# When nothing left, print the results.
if left == 0 and right == 0:
print results
return
# pos is the next postion we should insert parenthesis.
pos = num - left - right
if left > 0:
results[pos] = '('
print_paratheses(left - 1, right)
if left < right:
results[pos] = ')'
print_paratheses(left, right - 1)
def print_all_permutations(n):
global num
global results
num = n * 2
results = [None] * num
print_paratheses(n, n)
Ссылка: Перестановки круглых скобок
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);
}
In javascript / nodejs.
Программа изначально предназначалась для ответа на главный вопрос, но она идеально подходит для перечисления допустимых комбинаций скобок.
function* life(universe){
if( !universe ) yield '';
for( let everything = 1 ; everything <= universe ; ++everything )
for( let meaning of life(everything - 1) )
for( let question of life(universe - everything) )
yield question + '(' + meaning + ')';
}
let love = 5;
let answer = [...life(love)].length;
console.log(answer);
function brackets(n){
for( k = 1 ; k <= n ; k++ ){
console.log(...life(k));
}
}
brackets(5);
Рубиновая версия:
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)
Не самое элегантное решение, но именно так я и сделал в C++ (Visual Studio 2008). Используя набор STL для устранения дубликатов, я просто наивно вставляю пары new () в каждый строковый индекс в каждой строке предыдущего поколения, а затем рекурсивно.
#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;
}
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);
public static void printAllValidBracePermutations(int size) {
printAllValidBracePermutations_internal("", 0, 2 * size);
}
private static void printAllValidBracePermutations_internal(String str, int bal, int len) {
if (len == 0) System.out.println(str);
else if (len > 0) {
if (bal <= len / 2) printAllValidBracePermutations_internal(str + "{", bal + 1, len - 1);
if (bal > 0) printAllValidBracePermutations_internal(str + "}", bal - 1, len - 1);
}
}
//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);
}
}
}