生成Schröder路径

Question

我想生成从（0,0）到（2n，0）的schröder路径，没有高峰，即没有上升步骤，紧接着是下一步。 某些示例适用于n = 3：shröder paths。

/被编码为U， - 被编码为R和\被编码为D.这是我的代码来生成这些路径：

public static void addParen(List<String> list, int upstock,int rightstock,int  
     downstock,bool B, char[] str, int count,int total,int n) 
    { 


     if (total == n && downstock == 0) 
     { 
      String s = copyvalueof(str); 
      list.Add(s); 
     } 

     if (total > n || (total==n && downstock>0)) 
      return; 
     else 
     { 
      if (upstock > 0 && total<n) 
      { 
       str[count] = 'U'; 
       addParen(list, upstock - 1,rightstock, downstock+1,B=true, str, count + 1,total+1,n); 
      } 
      if (downstock > 0 && total<n && B==false) 
      { 
       str[count] = 'D'; 
       addParen(list, upstock,rightstock, downstock - 1,B=false, str, count + 1,total+1,n); 
      } 

      if (rightstock > 0 && total < n) 
      { 
       str[count] = 'R'; 
       addParen(list, upstock, rightstock-1, downstock, B = false, str, count + 1, total + 2,n); 
      } 
     } 
    } 

    public static List<String> generatePaths(int count) 
    { 

     char[] str = new char[count * 2]; 
     bool B = false; 
     List<String> list = new List<String>(); 
     addParen(list, count-1, count, 0,B,str, 0, 0,count*2); 
     return list; 
    } 

总为2n。我从n-1起始权利和零下降开始。因为没有up但我的bool B是假的（如果出现上涨，那么下跌不能到达它，所以为了防止这种情况，我把B = true，以防止它）如果上涨，那么应该有一个相应的下跌，并且总数应该增加1。如果正确的话，总数应该增加2.我的算法一般是这样工作的，但是我不能在这个实现中得到正确的结果。

Answer 1

最初的解决方案并不适应OP的需求，因为它太复杂，无法转换为JavaScript，其目的是展示解决这些问题的更好实践，而不是实际轻松解决这一问题。

但是，本着使用不变类型解决路径算法的精神，我们仍然可以以更简单的方式来实现：我们将使用string。

好一如既往，让我们建立我们的基础设施：工具，这将使我们的生活更轻松：

private const char Up = 'U'; 
private const char Down = 'D'; 
private const char Horizontal = 'R'; 
private static readonly char[] upOrHorizontal = new[] { Up, Horizontal }; 
private static readonly char[] downOrHorizontal = new[] { Down, Horizontal }; 
private static readonly char[] all = new[] { Up, Horizontal, Down }; 

和便利的小帮手方法：

private static IList<char> GetAllPossibleDirectionsFrom(string path) 
{ 
    if (path.Length == 0) 
     return upOrHorizontal; 

    switch (path.Last()) 
    { 
     case Up: return upOrHorizontal; 
     case Down: return downOrHorizontal; 
     case Horizontal: return all; 
     default: 
      Debug.Assert(false); 
      throw new NotSupportedException(); 
    } 
} 

记住，你的问题分解成小问题。所有困难问题​​都可以通过解决小问题来解决。这种辅助方法很难弄错;这很好，很难在简单的短方法中编写bug。

而现在，我们解决了更大的问题。我们不会使用迭代器块，因此移植更容易。我们会在这里使用一个可变列表来跟踪我们发现的所有有效路径。

我们的递归解决方案如下：

private static void getPaths(IList<string> allPaths, 
          string currentPath, 
          int height, 
          int maxLength, 
          int maxHeight) 
{ 
    if (currentPath.Length == maxLength) 
    { 
     if (height == 0) 
     { 
      allPaths.Add(currentPath); 
     } 
    } 
    else 
    { 
     foreach (var d in GetAllPossibleDirectionsFrom(currentPath)) 
     { 
      int newHeight; 

      switch (d) 
      { 
       case Up: 
        newHeight = height + 1; 
        break; 
       case Down: 
        newHeight = height - 1; 
        break; 
       case Horizontal: 
        newHeight = height; 
        break; 
       default: 
        Debug.Assert(false); 
        throw new NotSupportedException(); 
      } 

      if (newHeight < 0 /*illegal path*/ || 
       newHeight > 
        maxLength - (currentPath.Length + 1)) /*can not possibly 
                  end with zero height*/ 
        continue; 

      getPaths(allPaths, 
        currentPath + d.ToString(), 
        newHeight, 
        maxLength, 
        maxHeight); 
     } 
    } 
} 

不多说了，其漂亮的自我解释。我们可以减少一些论据; height不是严格必要的，我们可以在当前路径中计数ups和下降并计算出我们当前的高度，但这看起来很浪费。 maxLength也可以，也许应该删除，我们有足够的信息与maxHeight。

现在我们只需要一种方法来揭开这一关：

public static IList<string> GetSchroderPathsWithoutPeaks(int n) 
{ 
    var allPaths = new List<string>(); 
    getPaths(allPaths, "", 0, 2 * n, n); 
    return allPaths; 
} 

我们就大功告成了！如果我们把这个出去试驾：

var paths = GetSchroderPathsWithoutPeaks(2); 
Console.WriteLine(string.Join(Environment.NewLine, paths)); 

我们得到预期的结果：

URRD 
URDR 
RURD 
RRRR 

至于为什么你的解决方案不起作用？那么，只是你无法弄清楚这一事实说明了你现在的解决方案开始看起来多么复杂。当发生这种情况时，通常是一个好主意，可以退后一步，重新考虑你的方法，写下你的程序应该做的一步一步清晰的说明并重新开始。