Это пришло во время разговора с другом, и я подумал, что спрошу здесь, так как это интересная проблема и хотелось бы видеть решения других людей.
Задача состоит в том, чтобы написать функцию Brackets (int n), которая печатает все комбинации хорошо сформированных скобок из 1... n. Для скобок (3) выход будет
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
Взял трещину... С# тоже.
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);
}
}
Рекурсия использует тот факт, что вы никогда не можете добавить больше скобок открытия, чем желаемое количество пар, и вы никогда не сможете добавить больше закрывающих скобок, чем открывать скобки.
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")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Число возможных комбинаций - это каталонское число из N пар C (n).
Эта проблема была обсуждена на форумах joelonsoftware.com довольно эксцентрично, включая итеративные, рекурсивные и итеративные/битрейдерские решения. Там довольно классные вещи.
Вот краткое рекурсивное решение, предлагаемое на форумах на С#:
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);
Вывод:
()
(())()()
(())) (()()) (())()() (())()()()
Версия первого голосового ответа на 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)
Здесь другое решение 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 промаха, например "(()) (())". (Понятно, почему?) Я опубликую правильный (и более эффективный) алгоритм в ближайшее время.
(Позор всем вы, избиратели, не поймать меня!:))
Неэффективен, но короткий и простой. (Обратите внимание, что он только печатает строку "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 ^ "()"]
Пример:
Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Простое решение в С++:
#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
Ключ определяет правила, которые на самом деле довольно просты:
Это не печатает их, но создает список списков всех возможных структур. Мой метод немного отличается от других. Он реструктурирует решения до 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)
Вот решение в С++. Основная идея, которую я использую, заключается в том, что я беру вывод из предыдущего я (где я - число пар скобок) и передает это в качестве входных данных для следующего 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;
}
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, что является чем-то вроде линейного питона с актерской моделью с чертами. У меня нет возможности реализовать @memo, но вышеупомянутое работает без этой оптимизации)
Я попытался придумать изящный список monad-y для этого:
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
Groovy версия на основе вышеизложенного решения 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)")
}
""
}
Не самое элегантное решение, но именно так я и сделал это на С++ (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;
}
почему это не так просто, эта идея довольно проста
скобки (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;
}
}
//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);
}
}
}
рубиновая версия:
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)
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);
}
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);
}
}
Другой неэффективный, но элегантный ответ = >
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));
}
Попытка с memoization:
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];
}
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
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);
}
Caller - function(2*brackets, str, 0, 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)
Ссылка: Пермутации скобок
В С#
public static void CombiParentheses(int open, int close, StringBuilder str)
{
if (open == 0 && close == 0)
{
Console.WriteLine(str.ToString());
}
if (open > 0) //when you open a new parentheses, then you have to close one parentheses to balance it out.
{
CombiParentheses(open - 1, close + 1, str.Append("{"));
}
if (close > 0)
{
CombiParentheses(open , close - 1, str.Append("}"));
}
}
Мне был задан этот вопрос в интервью сегодня.
Я всегда пропустил этот вопрос в 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 (C n), где C n является Каталонский номер.
Временная сложность этого кода такая же, как и у другого высокопроизводительного решения, которое аналогично O (C n).