递归方法：我们如何生成括号上的所有可能性？

Question

我们怎样才能在大括号上生成所有可能性？

N值已经给了我们，我们要产生所有的可能性。

示例：

1) 如果 N == 1，则只有一种可能性 () 。

2) 如果 N==2，则可能性为 (())、()()

3) 如果 N==3，则可能性为 ((()))、(())()、()()( ), ()(()) ...

注意：左右大括号应该匹配。我的意思是 )( 对于 N==1 是无效的

我们可以通过使用递归方法来解决这个问题吗？

Answer 1

来自维基百科 -

Dyck 单词是由 ​​n 个 X 和 n 个 Y 组成的字符串，因此该字符串的初始段中 Y 的数量不会多于 X 的数量（另请参阅 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 单词进行排名和取消排名。我们强调
在编码与加泰罗尼亚语相关的对象时使用戴克词的重要性
数字。作为排名算法中使用的公式的结果
我们可以得到第n个Catalan数的递归公式。

Answer 2

对于给定的N，我们始终必须以左大括号开头。现在考虑它对应的右大括号在哪里。它可以位于中间，如 ()() 中，也可以位于末尾，如 (()) 中的 N=2。

现在考虑 N=3：

它可以位于末尾：(()()) 和 ((()))。

或者在中间：()(()) 和 ()()()，它位于位置 2。那么它也可以位于位置 4：(())()。

现在我们基本上可以将这两种情况结合起来，实现右大括号位于末尾的情况与位于中间的情况相同，但将 N=0 的所有可能性添加到末尾。

现在要解决这个问题，您可以计算出开始和结束大括号之间的 n 的所有可能性，类似地，您可以计算出结束大括号之后的 m 的所有可能性。 （注意m+n+1 = N）然后您可以组合所有可能的组合，将它们附加到您的可能性列表中，然后继续移动到端括号的下一个可能位置。

请注意，处理此类问题时很容易犯的错误是找到 i 和 Ni 的所有可能性，然后将它们组合起来，但这对于 N=3 会重复计算 ()()() 或至少打印两次。

下面是一些解决该问题的 Python 2.x 代码：

memoise = {}
memoise[0] = [""]
memoise[1] = ["()"]

def solve(N, doprint=True):
    if N in memoise:
        return memoise[N]

    memoise[N] = []

    for i in xrange(1,N+1):
        between = solve(i-1, False)
        after   = solve(N-i, False)
        for b in between:
           for a in after:
               memoise[N].append("("+b+")"+a)

    if doprint:
        for res in memoise[N]:
            print res

    return memoise[N]

Answer 3

递归解：

import java.util.Scanner;

public class Parentheses
{

    static void ParCheck(int left,int right,String str)
    {
            if (left == 0 && right == 0)
            {
                    System.out.println(str);
            }

            if (left > 0)
            {
                    ParCheck(left-1, right+1 , str + "(");
            }
            if (right > 0)
            {
                    ParCheck(left, right-1, str + ")");
            }

    }
    public static void main(String[] args)
    {
            Scanner input=new Scanner(System.in);
            System.out.println("Enter the  number");
            int num=input.nextInt();

            String str="";
            ParCheck(num,0,str);
    }
} 

Answer 4

下面的一些代码本质上是 JPvdMerwe 代码的紧凑版本，只不过它返回解决方案列表而不是打印它们。该代码适用于 Python 2 和 Python 3。

from itertools import product

def solve(num, cache={0: ['']}):
    if num not in cache:
        cache[num] = ['(%s)%s' % t for i in range(1, num + 1)
            for t in product(solve(i - 1), solve(num - i))]
    return cache[num]

# Test

for num in range(1, 5):
    print(num)
    for s in solve(num):
        print(s)

输出

1
()
2
()()
(())
3
()()()
()(())
(())()
(()())
((()))
4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
((()))()
(()()())
(()(()))
((())())
((()()))
(((())))

---

这里还有几个函数，源自 Ed Guness 链接的文章中给出的伪代码： acta.sapientia.ro/acta-info/C1-1/info1-9.pdf" rel="nofollow noreferrer">Dyck 词的生成和排名。该文章使用基于 1 的索引，但我已将它们转换为符合 Python 的基于 0 的索引。

这些函数比上面的 solve 函数慢，但它们可能仍然有用。 pos_dyck_words 的优点是它是纯粹迭代的。 unrank 是迭代的，但它调用递归辅助函数f； OTOH，f 使用缓存，所以它并没有那么慢，而且它只是缓存整数，它比 solve 的字符串缓存使用更少的 RAM。 unrank 的主要好处是它可以从索引号返回单个解决方案，而不必生成给定大小的所有解决方案。

此代码仅适用于 Python 3。将其转换为 Python 2 使用非常容易，您只需实现自己的缓存方案而不是 lru_cache 即可。您确实需要缓存，否则f对于除了最小的Dyck字长之外的所有字长来说都慢得难以忍受。

from itertools import product
from functools import lru_cache

# Generate all Dyck words of length 2*num, recursively
# fastest, but not lexicographically ordered
def solve(num, cache = {0: ['']}):
    if num not in cache:
        cache[num] = ['0%s1%s' % t for i in range(1, num + 1)
            for t in product(solve(i - 1), solve(num - i))]
    return cache[num]

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

# A helper function for `unrank`
# f(i, j) gives the number of paths between (0,0) and (i, j) not crossing
# the diagonal x == y of the grid. Paths consist of horizontal and vertical
# segments only, no diagonals are permitted

@lru_cache(None)
def f(i, j):
    if j == 0:
        return 1
    if j == 1:
        return i
    #if i < j:
        #return 0
    if i == j:
        return f(i, i - 1)
    # 1 < j < i <= n
    return f(i - 1, j) + f(i, j - 1)

# Determine the position array of a Dyck word from its rank number, 
# The position array gives the indices of the 1s in the word; 
# the rank number is the word's index in the lexicographic sequence
# of all Dyck words of length 2n 
# Very slow
def unrank(nr, n):
    b = [-1]
    for i in range(n):
        b.append(1 + max(b[-1], 2 * i))
        ni = n - i - 1
        for j in range(n + i - b[-1], 0, -1):
            delta = f(ni, j)
            if nr < delta or b[-1] >= n + i:
                break
            nr -= delta
            b[-1] += 1
    return b[1:]

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

# Generate all Dyck word position arrays for words of length 2*n, iteratively
def pos_dyck_words(n):
    b = list(range(1, 2 * n, 2))
    while True:
        yield b
        for i in range(n - 2, -1, -1):
            if b[i] < n + i:
                b[i] += 1
                for j in range(i + 1, n - 1):
                    b[j] = 1 + max(b[j - 1], 2 * j)
                break
        else:
            break

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

# Convert a position array to a Dyck word
def pos_to_word(b, n, chars='01'):
    c0, c1 = chars
    word = [c0] * (2 * n)
    for i in b:
        word[i] = c1
    return ''.join(word)

# Some tests

num = 4
print('num: {}, Catalan number: {}'.format(num, f(num, num)))

words = list(solve(num))
words.sort(reverse=True)
print(len(words))

for i, u in enumerate(pos_dyck_words(num)):
    v = unrank(i, num)
    w = words[i]
    ok = u == v and pos_to_word(u, num) == w
    print('{:2} {} {} {} {}'.format(i, u, v, w, ok))
print()

num = 10
print('num: {}, Catalan number: {}'.format(num, f(num, num)))

for i, u in enumerate(pos_dyck_words(num)):
    v = unrank(i, num)
    assert u == v, (i, u, v)
print('ok')

输出

num: 4, Catalan number: 14
14
 0 [1, 3, 5, 7] [1, 3, 5, 7] 01010101 True
 1 [1, 3, 6, 7] [1, 3, 6, 7] 01010011 True
 2 [1, 4, 5, 7] [1, 4, 5, 7] 01001101 True
 3 [1, 4, 6, 7] [1, 4, 6, 7] 01001011 True
 4 [1, 5, 6, 7] [1, 5, 6, 7] 01000111 True
 5 [2, 3, 5, 7] [2, 3, 5, 7] 00110101 True
 6 [2, 3, 6, 7] [2, 3, 6, 7] 00110011 True
 7 [2, 4, 5, 7] [2, 4, 5, 7] 00101101 True
 8 [2, 4, 6, 7] [2, 4, 6, 7] 00101011 True
 9 [2, 5, 6, 7] [2, 5, 6, 7] 00100111 True
10 [3, 4, 5, 7] [3, 4, 5, 7] 00011101 True
11 [3, 4, 6, 7] [3, 4, 6, 7] 00011011 True
12 [3, 5, 6, 7] [3, 5, 6, 7] 00010111 True
13 [4, 5, 6, 7] [4, 5, 6, 7] 00001111 True

num: 10, Catalan number: 16796
ok

Answer 5

我提出了以下算法，该算法不是按照 OP 的要求进行递归的，但鉴于其无敌的效率，值得一提。

正如 Ed Guness' 中所述 post，N 对正确匹配的括号组成的字符串是 Dyck 单词的表示。在另一种有用的表示中，括号(和)分别替换为1和0。因此，()()() 变为 101010。后者也可以看作是（十进制）数字42的二进制表示。总之，一些整数可以表示正确匹配的括号对的字符串。使用这种表示，以下是生成 Dyck 作品的有效算法。

令 integer 为任何 C/C++（或者可能是 C 系列编程语言）最长 64 位的无符号整数类型。给定一个 Dyck 单词，以下代码将返回下一个相同大小的 Dyck 单词（前提是它存在）。

integer next_dyck_word(integer w) {
    integer const a = w & -w;
    integer const b = w + a;
    integer c = w ^ b;
    c = (c / a >> 2) + 1;
    c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;
    return c;
} 

例如，如果 w == 42（二进制的 101010，即 ()()()），则函数返回 44（101100、()(())）。可以迭代，直到得到 56 (111000, ((())))，这是 N == 的最大 Dyck 单词3.。

上面，我提到了无敌的效率，因为就单个 Dyck 词的生成而言，该算法是 O(1)、无循环、无分支的。然而，实施仍有改进的空间。事实上，如果我们可以使用一些严格符合标准的 C/C++ 中不可用的汇编指令，则可以消除函数体中相对昂贵的除法 c / a。

你可能会说。 “反对！我不想受到 N <= 64 的限制”。好吧，我对此的回答是，如果您想生成所有 Dyck 作品，那么实际上您已经绑定了比 64 小得多的大小。事实上，戴克作品大小 N 的数量呈阶乘增长N 并且对于 N == 64 生成它们的时间可能比宇宙的年龄还要长。 （我承认我这次没有计算，但这是此类性质问题的一个非常常见的轶事特征。）

我写了一个 算法的详细文档。