插入语有效置换 [英] Valid Permutation of Parenthesis

问题描述

  

可能重复：
  解决递归问题（code卡塔）

给出一个算法来找到括号对给定的n所有有效置换 对于例如：

 对于n = 3，O / P应
{} {} {}
{{{}}}
{{}} {}
{} {{}}
{{} {}}
 

解决方案

问题概述

这是一个经典的组合问题表现在许多不同的方式。这些问题基本上是相同的：

• 生成所有可能的方式来平衡 N 双括号（即这个问题）
• 生成应用二元运算一切可能的办法， N + 1 因素
• 生成与所有的全二叉树 N + 1 叶
• 在许多人...

另请参见

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

---

一个简单的递归解决方案

下面是一个简单的递归算法来解决Java的这个问题：

 公共类括号{
    静态无效的括号（INT openStock，诠释closeStock，String s）将{
        如果（openStock == 0安培;＆安培; closeStock == 0）{
            的System.out.println（多个）;
        }
        如果（openStock大于0）{
            括号（openStock-1，closeStock + 1，S +＆所述;）;
        }
        如果（closeStock大于0）{
            括号（openStock，closeStock-1，S +＆gt;中）;
        }
    }
    公共静态无效的主要（字串[] args）{
        括号（3,0，）;
    }
}
 

上面打印（因为看到ideone.com ）：

 ＆LT;＆LT;＆LT;＆GT;＆GT;＆GT;
＆LT;＆LT;＆GT;＆LT;＆GT;＆GT;
＆LT;＆LT;＆GT;＆GT;＆LT;＆GT;
＆LT;＆GT;＆LT;＆LT;＆GT;＆GT;
＆LT;＆GT;＆LT;＆GT;＆LT;＆GT;
 

从本质上讲，我们跟踪关闭括号多少开放，是股票供我们使用，因为我们正在构建的字符串递归。

• 如果没有什么股票，该字符串是完全建立，你可以只把它打印出来
• 如果有股票提供一个开放的括号，尝试添加它。
  • 现在，你的少了一个开放的括号，但是的多了一个接近的括号来平衡它
• 如果有股票提供一个右括号，尝试添加它。
  • 现在，你少了一个右括号

请注意，如果你换，这样你尝试之前，你尝试添加一个左括号加上右括号递归的顺序，你只是得到了均衡的括号，但以相反的顺序相同的名单！ （见ideone.com ）。

---

一个最佳变种

上面的解决方案是非常简单和启发性的，但可以进一步优化。

最重要的优化是字符串建设方面。虽然它看起来像表面上简单的字符串连接，上述方案实际上有一个隐藏 O（N ^ 2）串建设部门（因为串联一个字符到一成不变的字符串长度 N 是 O（N）操作）。一般来说，我们优化此使用可变的StringBuilder 来代替，但对于这种特殊的情况下，我们也可以简单地用一个固定大小的的char [] 和首页变量。

我们还可以通过简化递归树优化。而不是递归的左右逢源在原有的解决方案，我们可以只递归单向，并做了另一种方式反复。

在下文中，我们已经做了两个优化，使用的char [] 和首页而不是字符串，只有递归加开括号，逐步添加右括号：（另见ideone.com）

 公共类Parenthesis2 {
    公共静态无效的主要（字串[] args）{
        支架（4）;
    }
    静态无效的括号（最终诠释N）{
        括号（N，0，0，新的char [N * 2]）;
    }
    静态无效的括号（INT openStock，诠释closeStock，INT指数和char [] ARR）{
        而（closeStock＆GT; = 0）{
            如果（openStock大于0）{
                ARR [指数] ='＆LT;';
                括号（openStock-1，closeStock + 1，指数+ 1，ARR）;
            }
            如果（closeStock--大于0）{
                ARR [指数++] ='＆GT;';
                如果（指数== arr.length）{
                    的System.out.println（ARR）;
                }
            }
        }
    }
}
 

递归逻辑是不太明显了，但两个最优化技术是有益的。

---

相关问题

• 检查字符串具有平衡括号
• 基本递归，检查平衡括号
• <一个href="http://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-giv">The可以用N键来创建的二进制搜索树的可能数量是由第N号加泰罗尼亚给出。为什么呢？

Possible Duplicate:
Solution to a recursive problem (code kata)

give an algorithm to find all valid permutation of parenthesis for given n for eg :

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

解决方案

Overview of the problem

This is a classic combinatorial problem that manifests itself in many different ways. These problems are essentially identical:

• Generating all possible ways to balance N pairs of parentheses (i.e. this problem)
• Generating all possible ways to apply a binary operator to N+1 factors
• Generating all full binary trees with N+1 leaves
• Many others...

See also

• Wikipedia/Catalan number
• On-Line Encyclopedia of Integer Sequences/A000108

---

A straightforward recursive solution

Here's a simple recursive algorithm to solve this problem in 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, "");
    }
}

The above prints (as seen on ideone.com):

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

Essentially we keep track of how many open and close parentheses are "on stock" for us to use as we're building the string recursively.

• If there's nothing on stock, the string is fully built and you can just print it out
• If there's an open parenthesis available on stock, try and add it on.
  • Now you have one less open parenthesis, but one more close parenthesis to balance it out
• If there's a close parenthesis available on stock, try and add it on.
  • Now you have one less close parenthesis

Note that if you swap the order of the recursion such that you try to add a close parenthesis before you try to add an open parenthesis, you simply get the same list of balanced parenthesis but in reverse order! (see on ideone.com).

---

An "optimized" variant

The above solution is very straightforward and instructive, but can be optimized further.

The most important optimization is in the string building aspect. Although it looks like a simple string concatenation on the surface, the above solution actually has a "hidden" O(N^2) string building component (because concatenating one character to an immutable String of length N is an O(N) operation). Generally we optimize this by using a mutable StringBuilder instead, but for this particular case we can also simply use a fixed-size char[] and an index variable.

We can also optimize by simplifying the recursion tree. Instead of recursing "both ways" as in the original solution, we can just recurse "one way", and do the "other way" iteratively.

In the following, we've done both optimizations, using char[] and index instead of String, and recursing only to add open parentheses, adding close parentheses iteratively: (see also on 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);
                }
            }
        }
    }
}

The recursion logic is less obvious now, but the two optimization techniques are instructive.

---

Related questions

• Checking string has balanced parentheses
• Basic Recursion, Check Balanced Parenthesis
• The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

这篇关于插入语有效置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！