括号的有效排列

Question

可能重复:
递归问题的解决方案(代码kata)

给出一个算法来查找给定n的括号的所有有效排列,例如:

for n=3, O/P should be
{}{}{} 
{{{}}}
{{}}{} 
{}{{}} 
{{}{}}

Answer 1

问题概述

这是一个经典的组合问题,它以许多不同的方式表现出来.这些问题基本相同:

• 生成平衡N括号对的所有可能方法(即此问题)
• 生成将二元运算符应用于N+1因子的所有可能方法
• 使用N+1叶子生成所有完整的二叉树
• 很多其他的...

也可以看看

• 维基百科/加泰罗尼亚语号码
• 在线整数序列百科全书/ A000108

一个简单的递归解决方案

这是一个简单的递归算法来解决Java中的这个问题:

public class Parenthesis {
    static void brackets(int openStock, int closeStock, String s) {
        if (openStock == 0 && closeStock == 0) {
            System.out.println(s);
        }
        if (openStock > 0) {
            brackets(openStock-1, closeStock+1, s + "<");
        }
        if (closeStock > 0) {
            brackets(openStock, closeStock-1, s + ">");
        }
    }
    public static void main(String[] args) {
        brackets(3, 0, "");
    }
}

以上打印(如ideone.com上所示):

<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

基本上我们跟踪有多少打开和关闭括号"库存"供我们使用,因为我们正在递归地构建字符串.

• 如果库存中没有任何东西,则字符串是完全构建的,您可以将其打印出来
• 如果库存中有可用的左括号,请尝试将其添加.
  • 现在你有一个较少的开括号,但还有一个更接近的括号来平衡它
• 如果库存中有一个紧密的括号,请尝试将其添加.
  • 现在你有一个不那么近的括号

请注意,如果您在尝试添加左括号之前交换递归的顺序,以便尝试添加一个紧密括号,则只需获得相同的平衡括号列表,但顺序相反!(见ideone.com).

"优化"变体

上述解决方案非常简单且具有指导性,但可以进一步优化.

最重要的优化是在字符串构建方面.虽然它看起来像表面上的简单字符串连接,但上面的解决方案实际上有一个"隐藏"的O(N^2)字符串构建组件(因为将一个字符连接到一个不可变String的长度N是一个O(N)操作).通常我们通过使用mutable StringBuilder来优化它,但对于这种特殊情况,我们也可以简单地使用固定大小char[]和index变量.

我们还可以通过简化递归树来优化.与原始解决方案中的"双向"递归不同,我们可以只递归"单向",并以迭代方式执行"其他方式".

在下文中,我们已经完成了两个优化,使用char[]和index替代String,并且仅递归以添加开括号,迭代地添加紧密括号:( 另见ideone.com)

public class Parenthesis2 {
    public static void main(String[] args) {
        brackets(4);
    }
    static void brackets(final int N) {
        brackets(N, 0, 0, new char[N * 2]);
    }
    static void brackets(int openStock, int closeStock, int index, char[] arr) {
        while (closeStock >= 0) {
            if (openStock > 0) {
                arr[index] = '<';
                brackets(openStock-1, closeStock+1, index+1, arr);
            }
            if (closeStock-- > 0) {
                arr[index++] = '>';
                if (index == arr.length) {
                    System.out.println(arr);
                }
            }
        }
    }
}

递归逻辑现在不太明显,但这两种优化技术是有益的.

相关问题

• 检查字符串具有平衡括号
• 基本递归,检查平衡括号
• 可以使用N个密钥创建的二叉搜索树的可能数量由第N个加泰罗尼亚数给出.为什么？

Answer 2

虽然不是一个真正的算法,但一个好的起点是加泰罗尼亚数字:

参考

• http://en.wikipedia.org/wiki/Catalan_number