Как напечатать все возможные сбалансированные скобки для выражения?

Question

Например, для элементов a,b,c,d существует 5 возможных способов взять соседние элементы и свести их в один элемент, где одновременно должны быть объединены ровно два элемента (ниже представлены в скобках):

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

Первый пример умножает a*b, затем умножает этот продукт на c, затем умножает этот продукт на d.Второй пример сначала умножает b*c, затем умножает этот продукт на a, затем умножает этот продукт на d.

Любое допустимое в скобках выражение 2n элементов обязательно будет иметь n ( и n ) со свойством, что при чтении слева направо всегда есть как минимум столько же (, сколько ),

Я знаю, что для n чисел число путей равно (n-1) -ому каталонскому числу .Но как точно сгенерировать все результирующие группировки?

Спасибо

(Кроме того: существует более 160 эквивалентных формулировок этой задачи, основанных на различных комбинаторных объектах, перечисленных каталонскими числами. Наиболее актуальный список из них см. Каталонское дополнение Ричарда Стэнли .)

Answer 1

Вот фактический код на Python, использующий генераторы, чтобы избежать использования слишком большого количества памяти.

#! /usr/bin/python

def parenthesized (exprs):
    if len(exprs) == 1:
        yield exprs[0]
    else:
        first_exprs = []
        last_exprs = list(exprs)
        while 1 < len(last_exprs):
            first_exprs.append(last_exprs.pop(0))
            for x in parenthesized(first_exprs):
                if 1 < len(first_exprs):
                    x = '(%s)' % x
                for y in parenthesized(last_exprs):
                    if 1 < len(last_exprs):
                        y = '(%s)' % y
                    yield '%s%s' % (x, y)

for x in parenthesized(['a', 'b', 'c', 'd']):
    print x

Answer 2

На самом деле существует более 5 скобок из 4 элементов;Вы на самом деле не имеете в виду «круглые скобки».Что вы действительно спрашиваете, так это количество различных способов, которыми N элементов могут быть reduce d, или количество деревьев, которые вы можете сделать из N элементов, сохраняя их порядок.

Это соответствуетподразделить выражение ровно N-1 раз.Например, на этом графике из статьи http://en.wikipedia.org/wiki/Catalan_number в Википедии, если у нас есть 4 элемента, есть ровно 5 способов применить к нему бинарный оператор (должно быть ровно 3 приложения, следовательно, ровно 3 узла):

Например, ((a*b)*c)*d, (a*(b*c))*d, (a*b)*(c*d), a*((b*c)*d), a*(b*(c*d))

Вот несколько кратких кодов Python для этого:

def associations(seq, **kw):
    """
        >>> associations([1,2,3,4])
        [(1, (2, (3, 4))), (1, ((2, 3), 4)), ((1, 2), (3, 4)), ((1, (2, 3)), 4), (((1, 2), 3), 4)] 
    """
    grouper = kw.get('grouper', lambda a,b:(a,b))
    lifter = kw.get('lifter', lambda x:x)

    if len(seq)==1:
        yield lifter(seq[0])
    else:
        for i in range(len(seq)):
            left,right = seq[:i],seq[i:] # split sequence on index i

            # return cartesian product of left x right
            for l in associations(left,**kw):
                for r in associations(right,**kw):
                    yield grouper(l,r)

Обратите внимание, как вы можетезамените интересную функцию на grouper этим кодом, например, grouper=list, или grouper=Tree, или grouper=....

Демо:

for assoc in associations('abcd'):
    print assoc

('a', ('b', ('c', 'd')))
('a', (('b', 'c'), 'd'))
(('a', 'b'), ('c', 'd'))
(('a', ('b', 'c')), 'd')
((('a', 'b'), 'c'), 'd')

Answer 3

Использовать рекурсию

   for each balanced expression of n-1 parentheses 
     for each pos i from 0 to m of an expression
       add '('
       for each pos  j from i + 1 to m
          add ')' if expression is balanced

Порядок, который вы получите, следующий:

n=0: 

n=1: ()

n=2: []() , [()]

n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}

Здесь я меняю парены каждый раз (,[,{, чтобы подчеркнуть, как работает алгоритм.

Answer 4

*

**Run this to generate all balanced parantheses:
//sudosuhan
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX_SIZE 200
void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3);
void printParenthesis(int n1 , int n2 , int n3 )
{
  if(n1 > 0 || n2 > 0 || n3 > 0)
     _printParenthesis(0, n1, 0, 0, n2, 0, 0, n3, 0, 0);
  return;
}
void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3)
{
  static char str[MAX_SIZE];     

  if(close1 == n1 && close2 == n2 && close3 == n3 ) 
  {
    printf("%s \n", str);
    return;
  }
  else
  {
    bool run1 = open1 > close1;
    bool run2 = open2 > close2;
    bool run3 = open3 > close3;
    if(run3)
    {
      str[pos] = ')';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3, close3+1);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
    }
    else if(run2 && !run3)
    {
      str[pos] = '}';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2+1, n3, open3, close3);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
    }
    else if(run1 && !run2 && !run3)
    {
      str[pos] = ']';
      _printParenthesis(pos+1, n1, open1, close1+1, n2, open2, close2, n3, open3, close3);

      if(open3 < n3)
      {
      str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
      if(open1 < n1)
      {
      str[pos] = '[';
      _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);
      }
    }
    else if(!run1 && !run2 && !run3)
    {
      if(open3 < n3)
      {
       str[pos] = '(';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);
      }
      if(open2 < n2)
      {
      str[pos] = '{';
      _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);
      }
      if(open1 < n1)
      {
      str[pos] = '[';
      _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);
      }
    }

  }
}
/* driver program to test above functions */
int main()
{
  int n1, n2, n3;
  n1 = 6;
  n2 = 1;
  n3 = 1;
  printParenthesis(n1, n2, n3);
  return 0;
}**

*

Answer 5

import java.util.ArrayList;


public class Parantheses {

    private ArrayList<String> parStringList;
    private int total;

    public void exploreParantheses(String parString,int leftCnt,int rightCnt)
    {
        if (leftCnt < total)
        {
            exploreParantheses(parString + "(", leftCnt+1, rightCnt);
        }
        if ((rightCnt < total) &&(rightCnt < leftCnt))
        {
            exploreParantheses(parString + ")", leftCnt, rightCnt+1);
        }
        else if (rightCnt == total)
        {
            parStringList.add(parString);
        }
    }
    public ArrayList<String> generateParanthesis(int numPars)
    {
        this.total = numPars;
        this.parStringList = new ArrayList<String>();
        exploreParantheses("", 0, 0);
        return this.parStringList;
    }
    public static void main(String args[])
    {
        ArrayList<String> par;
        par = (new Parantheses()).generateParanthesis(6);
        for (String str: par)
            System.out.println(str);
    }
}

Answer 6

Рекурсия была бы способом пойти

разделить abcd на

(a) (bcd)
(ab) (cd)
(abc) (d)

Вот некоторые из возможностей

Теперь рекурсивно вы можете разделить каждую строку (игнорируя скобки при разделении), скажем, для (bcd) одна возможность

(b) (cd)

так что теперь другая комбинация

((a)(b)(cd))

Вы можете остановить дерево рекурсии, когда получите строку только с одним алфавитом

Answer 7

У начальной левой круглой скобки есть уникальная совпадающая правая круглая скобка, так что то, что находится между двумя круглыми скобками и что следует после, является допустимыми выражениями.Это приводит к простому рекурсивному решению, выраженному здесь в Scala.

def catalan(n: Int): List[String] =
    if (n == 0) List("")
    else
        for {
            k <- (0 to n - 1).toList
            first <- catalan(k)
            rest <- catalan(n - 1 - k)
        } yield "a" + first + "b" + rest

Здесь я использую «a» для левой скобки и «b» для правой скобки.

catalan(0)               List()
catalan(1)               List(ab)
catalan(2)               List(abab, aabb)
catalan(3)               List(ababab, abaabb, aabbab, aababb, aaabbb) 
catalan(5).size          42

Answer 8

Вот версия C # генерации всех возможных сбалансированных строк в скобках из заданных коэффициентов n + 1.

Примечание. Решение проблемы в основном удовлетворяет каталонскому рекурсивному соотношению (более подробно вы можете обратиться к http://codingworkout.blogspot.com/2014/08/all-possible-paranthesis.html, http://en.wikipedia.org/wiki/Catalan_number)

string[] CatalanNumber_GeneratingParanthesizedFactorsRecursive(string s)
        {
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            if(s.Length == 2)
            {
                string r = "(" + s + ")";
                return new string[] { r };
            }
            List<string> results = new List<string>();
            for (int i = 1; i < s.Length; i++)
            {
                var r1 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(0, i));
                var r2 = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                    s.Substring(i));
                foreach(var s1 in r1)
                {
                    foreach(var s2 in r2)
                    {
                        string r = "(" + s1 + s2 + ")";
                        results.Add(r);
                    }
                }
            }
            return results.ToArray();
        }

, где

string[] CatalanNumber_GeneratingParanthesizedFactors(string s)
        {
            s.ThrowIfNullOrWhiteSpace("s");
            if(s.Length == 1)
            {
                return new string[] {s};
            }
            var r = this.CatalanNumber_GeneratingParanthesizedFactorsRecursive(
                s);
            return r;
        }

И юнит-тесты

[TestMethod]
        public void CatalanNumber_GeneratingParanthesizedFactorsTests()
        {
            var CatalanNumbers = new int[] { 1, 1, 2, 5, 14, 42, 132, 429, 
                1430, 4862, 16796 };
            string input = "";
            for (int i = 1; i <= 10; i++)
            {
                input += i;
                var results2 = this.CatalanNumber_GeneratingParanthesizedFactors(input);
                Assert.AreEqual(results2.Length, CatalanNumbers[input.Length-1]);
                Debug.WriteLine("-----------------------------------------------");
                foreach (string ss in results2)
                {
                    Debug.WriteLine(ss);
                }
            }
            string s = "a";
            var r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual(r.Length, 1);
            Assert.AreEqual(s, r[0]);
            s = "ab";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            Assert.AreEqual("(ab)", r[0]);
            s = "abc";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);
            string[] output = new string[] { "(a(bc))", "((ab)c)" };
            Assert.AreEqual(2, r.Length);
            foreach(var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
            s = "abcd";
            r = this.CatalanNumber_GeneratingParanthesizedFactors(s);

            output = new string[] { "(a(b(cd)))", "(a((bc)d))", "((ab)(cd))", "(((ab)c)d)", "((a(bc))d)"};
            Assert.AreEqual(5, r.Length);
            foreach (var o in output)
            {
                Assert.AreEqual(1, r.Where(rs => (rs == o)).Count());
            }
        }

Answer 9

И вот код C ++ для того же самого:

bool is_a_solution( string partial,int n,int k) { 
if(partial.length() == n*2 )  
 return true;
return false;
  }
string constructCandidate(int n,string input,string partial, int k) { 
int xcount=0,ycount=0;
int count;
int i;
string candi;
if(k == 0)  
    return string("(");
else { 
    for(i=0;i<partial.length();i++)  { 
        if( partial[i] == '(') xcount++;
        if( partial[i] == ')') ycount++;
    }
    if( xcount  <n) candi+="(";  
    if( ycount < xcount) candi+=")"; 
    }
return candi;}                                                                                void backTrack(int n,string input, string partial,int k )  { 
int i, numCanditate;
string mypartial;
    if( is_a_solution(partial,n,k)) { 
    cout <<partial<<"\n"; 
 }else {
     string  candi=constructCandidate(n,input,partial,k); 
     for(i=0;i<candi.length();i++) {
         backTrack(n,input,partial+candi[i],k+1); 
     }
 }
void paranthesisPrint(int n){
   backTrack(n,"()", "",0); 
   }