打印n对括号的所有有效格的算法 [英] Algorithm to print all valid combations of n pairs of parenthesis

问题描述

我正在处理问题陈述中所述的问题.我知道我的解决方案是正确的(运行程序)，但是我是否在正确地分析我的代码(以下)很好奇.

  def parens(num)如果num == 1，则返回[()"]paren_arr = []parens(num-1).each做| paren |paren_arr<<paren +()"，除非()#{paren}" ==#{paren}()"paren_arr<<()#{paren}"paren_arr<<(## paren})"结尾paren_arr结尾 

例如，

parens(3)将输出以下内容:

  [()()()"，(()())"，(())()"，()(())"，((()))] 

这是我的分析:每个f(n)值大约是f(n-1)的3倍.所以:

f(n)= 3 * f(n-1)= 3 * 3 * f(n-2)〜(3 ^ n)时间成本.通过类似的分析，堆栈将被f(1).. f(n)占据，因此空间复杂度应为3 ^ n.

我不确定时间或空间的分析是否正确.一方面，堆栈仅包含n个函数调用，但是这些调用中的每一个返回的数组都是其之前调用的〜3倍.这会影响空间成本吗?我的时间分析正确吗?

解决方案

正如其他人提到的那样，您的解决方案是不正确的.

我最喜欢的解决方案是通过将当前字符串重复递增到词法上的下一个有效组合来生成所有有效组合.

词法上的下一步"分解为几条使其变得非常简单的规则:

• 字符串中的第一个差异将'('更改为')'.否则，下一个字符串将在词汇上在当前字符串之前.

• 第一个区别是尽可能地靠近右侧.否则，增量将较小.

• 在第一个差异之后的部分在词汇上最小，同样是因为否则将有较小的增量.在这种情况下，这意味着所有'('都在所有')之前.

因此，您要做的就是找到最右边的'('，可以将其更改为')'，将其翻转，然后附加正确数量的'('s和')'s.

我不了解Ruby，但是在Python中看起来像这样:

  current =((((())))"而True:打印(当前)打开= 0关闭= 0pos = 0对于范围(len(current)-1，-1，-1)中的i:如果current [i] ==')':关闭+ = 1别的:打开+ = 1如果关闭>打开:pos = i休息如果pos< 1:休息当前=当前[:pos] +)" +(" *打开+)" *(关闭-1) 

输出:

 ((((())))((()()))((())())((()))()(()(()))(()()())(()())()(())(())(())()()()(((()))()(()())()(())()()()(())()()()() 

对于许多类型的生成所有组合"问题，这样的解决方案变得简单快捷.

I'm working on the problem stated in the question statement. I know my solution is correct (ran the program) but I'm curious as to whether or not I'm analyzing my code (below) correctly.

def parens(num)
  return ["()"] if num == 1
  paren_arr = []
  parens(num-1).each do |paren| 
    paren_arr << paren + "()" unless "()#{paren}" == "#{paren}()"
    paren_arr << "()#{paren}"
    paren_arr << "(#{paren})"
  end
  paren_arr
end

parens(3), as an example, will output the following:

["()()()", "(()())", "(())()", "()(())", "((()))"]

Here's my analysis: Every f(n) value is roughly 3 times as many elements as f(n-1). So:

f(n) = 3 * f(n-1) = 3 * 3 * f(n-2) ~ (3^n) time cost. By a similar analysis, the stack will be occupied by f(1)..f(n) and so the space complexity should be 3^n.

I'm not sure if this analysis for either time or space is correct. On the one hand, the stack only holds n function calls, but each of these calls returns an array ~3 times as big as the call before it. Does this factor into space cost? And is my time analysis correct?

解决方案

As others have mentioned, your solution is not correct.

My favourite solution to this problem generates all the valid combinations by repeatedly incrementing the current string to the lexically next valid combination.

"Lexically next" breaks down into a few rules that make it pretty easy:

• The first difference in the string changes a '(' to a ')'. Otherwise the next string would be lexically before the current one.

• The first difference is as far to the right as possible. Otherwise there would be smaller increments.

• The part after the first difference is lexically minimal, again because otherwise there would be smaller increments. In this case that means that all the '('s come before all the ')'.

So all you have to do is find the rightmost '(' that can be changed to a ')', flip it, and then append the correct number of '('s and ')'s.

I don't know Ruby, but in Python it looks like this:

current="(((())))"
while True:
    print(current)
    opens=0
    closes=0
    pos=0
    for i in range(len(current)-1,-1,-1):
        if current[i]==')':
            closes+=1
        else:
            opens+=1
            if closes > opens:
                pos=i
                break
    if pos<1:
        break
    current = current[:pos]+ ")" + "("*opens + ")"*(closes-1)

Output:

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Solutions like this turn out to be easy and fast for many types of "generate all the combinations" problems.

这篇关于打印n对括号的所有有效格的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！