复发方法：我们如何在大括号上产生所有可能性？ [英] Recurrence Approach : How can we generate all possibilities on braces?
问题描述
我们如何在大括号上产生所有可能性？
N值给了我们，我们必须产生所有的可能性。
示例：
1）如果N == 1，那么只有一个可能性（）。
2）如果N == 2，那么可能性是（（）），（）（）
$ b $如果N == 3，则可能性为（（）），（（））（），（）（）（），（）（（））...
注意：左右括号应该匹配。我的意思是（对于N == 1是无效的）
我们可以使用重现方法来解决这个问题吗？
从维基百科 -
Dyck字是一个由n X和n Y使得字符串的初始段不比X的Y（参见Dyck语言），例如，以下是长度为6的Dyck单词：
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
将符号X重新解释为开括号，Y作为右括号，Cn计算包含正确匹配的n对括号的表达式数：
< （）（）（）（）（）（）（）（）（）（（）（）（）（（） ））
另请参见 http：//www.acta .sapientia.ro / acta-info / C1-1 / info1-9.pdf
摘要。提出了一种生成所有Dyck单词的新算法，
用于排序和排序Dyck单词。我们强调在与Catalan
数字相关的编码对象中使用Dyck词的
重要性。作为排序算法
中使用的公式的结果，我们可以获得第n个加泰罗尼亚人的递归公式。
How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
Examples:
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
Can we solve this problem by using recurrence approach ?
解决方案From wikipedia -
A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:
((())) ()(()) ()()() (())() (()())See also http://www.acta.sapientia.ro/acta-info/C1-1/info1-9.pdf
Abstract. A new algorithm to generate all Dyck words is presented, which is used in ranking and unranking Dyck words. We emphasize the importance of using Dyck words in encoding objects related to Catalan numbers. As a consequence of formulas used in the ranking algorithm we can obtain a recursive formula for the nth Catalan number.
这篇关于复发方法：我们如何在大括号上产生所有可能性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
