Prolog, generate all combinations of n balanced brackets

Question

Can you show me how to implement an algorithm in PROLOG to generate all combinations of N balanced brackets? ( brackets which close correctly )

Answer 1

This is what dcgs are best for. We define a grammar for balanced round brackets and then enumerate them accordingly.

:- set_prolog_flag(double_quotes, chars).

balanced --> "".
balanced --> "(", balanced, ")", balanced.

Now, when asking for concrete sentences, it is best to use library(double_quotes) see this for more.

We can ask for sentences of a fixed length:

?- length(T, 6), phrase(balanced, T).
   T = "()()()"
;  T = "()(())"
;  T = "(())()"
;  T = "(()())"
;  T = "((()))"
;  false.

Or just abound any sentence:

?- length(T, N), phrase(balanced, T).
   T = [], N = 0
;  T = "()", N = 2
;  T = "()()", N = 4
;  T = "(())", N = 4
;  T = "()()()", N = 6
;  T = "()(())", N = 6
;  T = "(())()", N = 6
;  T = "(()())", N = 6
;  T = "((()))", N = 6
;  T = "()()()()", N = 8
;  T = "()()(())", N = 8
;  T = "()(())()", N = 8
;  T = "()(()())", N = 8
;  T = "()((()))", N = 8
;  ... .

Answer 2

Here is another solution to get the Catalan numbers.
It places the parenthesis similar to the DCG solution:

catalan(L) :-
   append(['('|A], [')'|B], L),
   length(A, N), 0 =:= N mod 2,
   catalan(A),
   catalan(B).
catalan([]).

Example, verifies 3 entries from A000108:

?- length(L, 18), findall(L, catalan(L), R), 
   length(R, N), write(N), nl, fail; true.
4862
?- length(L, 20), findall(L, catalan(L), R), 
   length(R, N), write(N), nl, fail; true.
16796
?- length(L, 22), findall(L, catalan(L), R), 
   length(R, N), write(N), nl, fail; true.
58786

Answer 3

here is a backtracking solution

paran(N, N, N, []).
paran(N, O, C, ['('|R]) :-
    C1 is C + 1,
    C1 =< N,
    paran(N, O, C1, R).
paran(N, O, C, [')'|R]) :-
    O1 is O + 1,
    O1 =< C,
    paran(N, O1, C, R).

generate(N, R) :- paran(N, 0, 0, R).

paran is the main function, first argument is the number of balanced brackets, second and third are the number of opened and closed brackets respectively, and in R we store the result. generate will call paran with 0 as second argument and also third argument since we start with 0 opened and 0 closed brackets, and the algorithm stops when we get to n opened and n closed brackets

?- generate(2, R).
R = ['(', '(', ')', ')'] ;
R = ['(', ')', '(', ')'] ;
false.

if you want all the results in a list, you can use it with findall

?- findall(R, generate(2, R), L).
L = [['(', '(', ')', ')'], ['(', ')', '(', ')']].

Answer 4

#include<iostream>
using namespace std;
void parenthesis(int open, int close, string brak)
{
   if (open == 0 && close == 0)
      cout<<brak;
   if (open>close)
      return;
   if (open > 0)
      parenthesis(open - 1, close,brak + "(");
   if (close > 0)
      parenthesis(open, close-1 ,brak + ")");
}
void printPar(int n)
{
   parenthesis(n,n,"\n");
}
int main()
{
   int n = 3;
   printPar(n);
   return  0;

}