主页 / 问题 / 1541502
Accepted
Глеб
Asked:2023-09-19 20:20:13 +0000 UTC2023-09-19 20:20:13 +0000 UTC

Python。生成所有平衡的括号组合

  • 772

健康）状况

n您需要编写一个函数来生成括号对的“平衡”组合的完整列表。平衡组合是指每个左括号必须有一个对应的右括号，并且右括号不能出现在对应的左括号之前。

输入数据：

输入是 0 到 15 之间的正整数（实际上是n）（类型int）。

输出

输出应该是平衡括号字符串的完整列表（类型list）（参见示例）。

例子：

0 => [""]

1 => ["()"]

2 => ["()()","(())"]

3 => ["()()()","(())()","()(())","(()())","((()))"]

评价标准：

竞赛语言为Python 3。

最快的解决方案将赢得竞争。

来源：

来源是Codewars All Balanced Parentheses 4 kyu 难度的问题。

聚苯乙烯

如果我以某种方式错误地设置了竞赛格式，我将很乐意接受更正和澄清。

UPD： 以下代码用于打发时间：

import time

def count_time(function, f_arg, how_many_times):
    a = time.time()
    for i in range(how_many_times):
        function(f_arg)
    b = (time.time() - a) / how_many_times
    return b

结果：

  • 第一个解决方案@MBo：26.08478112220764

  • 第二个解决方案@MBo：（我相信它，我没有检查它，我们假设它是 10,000 秒。）

  • 第一个解决方案@StanislavVolodarskiy：（在第六次迭代时，计算机冻结并且算法未完成）

  • 第二个解决方案@StanislavVolodarskiy：4.338251447677612

总的来说，根据 StanislavVolodarskiy 性质的迭代构建获胜！我接受他的回答。

python

2 个回答

  1. 用于底漆。13 秒生成 1000 万个选项（n=15）。

    使用一种算法按字典顺序查找下一个排列（这是一个类似的例子）

    搜索的是最右边的左括号，该左括号可以用右括号替换，而不会影响正确的平衡（任何前缀中右括号的数量不应超过左括号的数量）。右侧的变量负责计算余额bal。如果大于零，那么右边的右括号就多了，左边的左括号也相应多了，那么就可以把当前的左括号改为右括号了。之后，我们从一组左括号中添加按字典顺序排列的最小后缀（它们的数量是根据余额计算的），然后是一组右括号。

    import time
def next_seq(s, n):
    bal = 0
    for i in reversed(range(2*n)):
        if s[i] == "(":
            bal -= 1
            if bal:
                op = n-(i+bal)//2
                cl = 2*n-i-1 - op
                return s[:i] + ')' + "("*op + ")"*cl
        else:
            bal += 1
    return ""

n = 15
res = []
t = time.time()
s = "("*n + ")"*n
while s:
    res.append(s)
    s = next_seq(s, n)
print(time.time()-t, len(res))
#print(res)

    n=3 的输出：

    ['((()))', '(()())', '(())()', '()(())', '()()()']

    到堆：根据 Knuth 的说法，我生成了与有效括号序列相对应的二进制单词，但即使不生成字符串，它也一点也不快

    def next_p(x):
    m0 = 0xFFFFFFFF // 3
    t = x ^ m0
    if ((t&x)==0):
        return 0
    u = (t-1) ^ t
    v = x | u
    y = (u & m0).bit_count()
    #y = bin(u & m0).count("1")   #до Python 3.10
    w = v + 1
    t = v & ~w
    y = t >> y
    y += w
    return y

def p2str(x):
    s, j = 0, 0
    res = []
    while x:
        s += -1 + 2*(x&1)
        res.append(")("[x&1])
        x >>= 1
        j += 1
    res = "".join(res)
    res += ")"*s
    return res

x = (1<<n) - 1
while x:
    #print(p2str(x))
    #res.append(p2str(x))
    x = next_p(x)
    • 5
  2. Best Answer

    通过确定正确的括号顺序进行递归构造。为了加速递归，最后十二个字符的尾部被缓存。缓存大小不超过50 KB ( 12·2 12 )。

    def parens_search(n, cb):
    m = min(n, 12) + 1
    tails = [[None] * m for _ in range(m)]
    tails[0] = [[')' * r] for r in range(m)]

    for l in range(1, m):
        for r in range(l, m - l):
            tails[l][r] = []
            if r > l:
                tails[l][r].extend(')' + t for t in tails[l][r - 1])
            if l > 0:
                tails[l][r].extend('(' + t for t in tails[l - 1][r])

    def rec(head, l, r):
        if l + r < m:
            for t in tails[l][r]:
                cb(head + t)
        else:
            if r > l:
                rec(head + ')', l, r - 1)
            if l > 0:
                rec(head + '(', l - 1, r)

    rec('', n, n)


def parens(n):
    result = []
    parens_search(n, result.append)
    return result

        n       15    16    17
время (c)  1.3   4.8  17.3

    按属性迭代构建：

    def parens(n):
    parens = [['']]
    for m in range(1, n + 1):
        parens.append([
            f'({lhs}){rhs}'
            for i in range(m)
            for lhs in parens[i]
            for rhs in parens[m - i - 1]
        ])
    return parens[-1]

        n       15    16    17
время (c)  2.3   8.3  29.6
    • 4

相关问题