计算算法的复杂性以打印 n 对括号的所有有效（即正确打开和关闭）组合

Question

我想听听您对我实施的这个算法的时间和 space 复杂度的意见（在 Python 中），以计算打印所有有效（即正确打开和关闭）的算法的复杂度) n 对括号的组合（参见 all valid combinations of n-pair of parenthesis）

def find_par_n(n):
    s = set(["()"])
    for i in range(2, n + 1):
        set_to_add = set()
        for str_ in s:
            set_temp = set()
            ana = set()
            for j in range(len(str_) + 1):
                str_c = str_[0:j] + '(' + str_[j:]
                if str_c in ana:
                    continue
                ana.add(str_c)
                for k in range(j + 1, len(str_) + 1):
                    str_a = str_c
                    str_a = str_a[0:k] + ')' + str_a[k:]
                    set_temp.add(str_a)
            set_to_add.update(set_temp)
        s = set_to_add
    return s

算法很可能可以在时间和 space 方面得到改进。请分享您的想法。

Answer 1

让我们尝试使用更简单的版本。

一些定理：

正确配对的字符串是偶数长度。请不要让我证明这一点。
给定一个正确配对的长度为 2k 的字符串，可以通过在字符串中每个可能的位置插入一对括号 '()' 来构造所有长度为 2(k + 1) 的字符串。有2k + 1个这样的职位。
要生成所有 n 对，我们需要递归到插入步骤 n 次（并得到长度为 2n.

请注意，这不足以生成所有唯一正确配对的字符串，因为例如将 () 插入 () 会产生两次相同的字符串 (()())。然而，作为上限，它应该足够了。

def add_parens(s, nparens):    
    if not s:    
       add_parens('()', nparens)    
    max_length = 2 * nparens    
       if len(s) == max_length:    
       print(s)    
    else:    
        for i in range(0, len(s)):    
            add_parens(s[0:i] + '()' + s[i:], nparens)    

n = 5      
add_parens('', n)

时间复杂度：

空字符串有 1 个插入点。
() 有 3 个插入点。 ...

总而言之：

T(n) = 1 * 3 * ... * 2n + 1 ~ O(n!)

Space 递归版本的复杂度为 O(n(2n + 1))，但我很确定可以将其降低为线性。

Answer 2

我很好奇并写了我自己的版本。以下是一些规格（这些都在 Python 2.7 中）：

`n=8`

我的：21 毫秒

你的：89 毫秒

`n=10`

我的：294 毫秒

你的：1564 毫秒

def get(n):
    
    def find(current):
        out = []
        last_index = 0
        for j in range(current.count('(')):
            last_index = current.index('(',last_index) + 1
            out.append(current[:last_index] + '()' + current[last_index:])
        return out
        
    seed = '()'
    current = '()'
    temp = set(['()'])
    for i in range(n):
        new = set()
        for thing in temp:
            new.update(find(thing))
        temp = new

    return [a[1:-1] for a in temp]

我认为最大的区别是我的只有 3 个 for 循环，而你的有 4 个。这发生在 str.count 函数中。使用这个内置的可能对速度有很大的贡献。此外，在每个阶段之后，我都确定了重复项，这按时成倍减少了。

其实我看到最大的区别是我只在括号后插入，完成后把外面两个去掉。它创建的重复项更少。因此 ((())()) 被创建，并在删除封闭的 ().

后缩减为 (())() 的正确形式

Answer 3

递归版本看起来很简单，只在有效分支上花费时间：

def gen(sofar, l, r, n):
    """
    sofar: string generated so far
    l: used left parentheses
    r: used right parentheses
    n: total required pairs
    """
    result = []
    if l == n and r == n:
        # solution found
        result.append(sofar)
    else:
        if l > r:
            # can close
            result.extend(gen(sofar + ")", l, r + 1, n))
        if l < n:
            # can open
            result.extend(gen(sofar + "(", l + 1, r, n))
    return result

def generate(n):
    return gen("", 0, 0, n)

print generate(4)

Answer 4

为获得最佳效果，请避免设置。如果每种可能性只生成一次，则可以将它们放入一个向量中。

这是一个非常简单的递归，它比@bcdan 的回答稍慢：

def rget(n):
  if n == 0:
    return ['']
  else:
    return [fst + '(' + snd + ')' for i in range(n)
                                  for fst in rget(i)
                                  for snd in rget(n-i-1)]

如果你想要一个生成器而不是一个完整的结果列表，上述的变体可能是理想的，但对于一个完整列表的情况，从 0 计算每个 j 的结果要快得多到 n，使用先前计算的列表而不是递归调用：

def iget(n):
  res = [['']]
  for j in range(1, n+1):
    res.append([fst + '(' + snd + ')' for i in range(j)
                                      for fst in rget(i)
                                      for snd in rget(j-i-1)])
  return res[n]

事实证明这要快一个数量级（使用 Python 3.3.2）。

为什么有效

您可以将任何平衡字符串分解为两个平衡子字符串。这不是唯一分解，但可以通过选择尽可能短的非空平衡后缀使其唯一。最短的非空平衡后缀具有起始 ( 与结束 ) 匹配的属性；如果不是这种情况，它可以分解为两个更短的非空平衡序列。因此，递归包括查找 Fst(Snd) 形式的所有序列，其中 Fst 和 Snd 的大小之和为 n-1.

时间复杂度：

有n对括号的平衡数列是第n^thCatalan number C_n,即O(4ⁿn^2/3)。上面的代码在 O(n) 中生成每个序列（因为字符串连接需要 O(n) 时间）总复杂度为 O( 4ⁿn^5/3)

Answer 5

可能的组合数是加泰罗尼亚数。所以复杂度至少是那个数字指定的那个。 https://en.wikipedia.org/wiki/Catalan_number

计算算法的复杂性以打印 n 对括号的所有有效（即正确打开和关闭）组合

Calculating the complexity of algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses

python

algorithm

catalan

`n=8`

`n=10`

为什么有效

时间复杂度：