我们如何在大括号上生成所有可能性？
N值已经给了我们，我们必须产生所有的可能性。
例子：
1) 如果 N == 1，那么只有一种可能性 () 。
2）如果N==2，那么可能性是（（）），（）（）
3) 如果 N==3，那么可能性是 ((())), (())(),()()(), ()(()) ...
注意：左右大括号应该匹配。我的意思是 )( 对于 N==1 无效
我们可以使用递归方法解决这个问题吗？
问问题
2416 次
5 回答
4
对于给定的N，我们总是必须从一个开括号开始。现在考虑它对应的右括号在哪里。它可以像 in 一样在中间，也可以像for一样在()()末尾。(())N=2
现在考虑N=3：
它可以在最后：(()())和((()))。
或者在中间：()(())以及()()()它在位置 2 的位置。那么它也可以在位置 4: (())()。
现在我们可以通过实现右大括号在末尾的情况与它在中间的情况相同，基本上可以结合这两种情况，但在末尾添加了 N=0 的所有可能性。
现在要解决它，您可以计算出n开始和结束大括号之间的所有可能性，同样您可以计算出m结束大括号之后的所有可能性。（注意m+n+1 = N）然后您可以组合所有可能的组合，将它们附加到您的可能性列表中，然后移动到下一个可能的位置以放置端括号。
请注意，处理这些类型的问题时容易犯的一个错误是找到所有的可能性 fori和 forN-i并将它们组合起来，但这 forN=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]
于 2010-11-30T13:34:31.483 回答
4
来自维基百科 -
一个 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词进行排序和去排序。我们强调使用 Dyck 词对与加泰罗尼亚数字相关的对象进行编码的重要性。作为排名算法中使用的公式的结果，我们可以获得第 n 个加泰罗尼亚数的递归公式。
于 2010-11-30T13:34:46.887 回答
2
我想出了以下算法，它不是 OP 要求的递归算法，但鉴于其无敌的效率，值得一提。
正如Ed Guiness 的 帖子中所说，成对正确匹配的括号字符串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;
}
例如，if w == 42(101010在二进制中，即()()()) 函数返回44( 101100, ()(()))。可以迭代直到得到56( 111000, ((()))) ，这是 的最大 Dyck 词N == 3。
上面，我提到了无敌的效率，因为就单个 Dyck 词的生成而言，这个算法是 O(1)，无环和无分支的。但是，实施仍有改进的余地。c / a事实上，如果我们可以使用一些在严格符合标准的 C/C++ 中不可用的汇编指令，则可以消除函数体中相对昂贵的划分。
你可能会说。“反对！我不想被束缚N <= 64”。好吧，我对此的回答是，如果你想生成所有 Dyck 作品，那么实际上你已经绑定到比64. 事实上，Dyck 作品的数量N随着产生它们N的N == 64时间而倍增，它们的生成时间很可能大于宇宙的年龄。（我承认我没有计算这个时间，但这是这种性质的问题的一个非常普遍的轶事特征。）
我已经写了一份关于算法的详细文档。
于 2019-05-05T14:06:12.357 回答
2
这里的一些代码本质上是 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 Guiness 链接的文章中给出的伪代码：Dyck words 的生成和排名。那篇文章使用基于 1 的索引，但我已将它们转换为符合 Python 的基于 0 的索引。
这些函数比solve上面的函数慢，但它们可能仍然有用。pos_dyck_words具有纯迭代的优点。unrank是迭代的，但它调用递归辅助函数f；OTOH，f使用缓存，所以它没有尽可能慢，而且它只缓存整数，它使用的 RAM 比solve. 的主要好处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
于 2016-12-24T06:37:06.153 回答
1
递归解决方案：
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);
}
}
于 2013-08-06T04:43:03.660 回答