生成施罗德路径

Question

我想用生成从(0，0)到(2n，0)的schröder路径没有峰值，即没有上升步骤，紧接着是下降步骤。一些例子适用于n=3:shröder路径。

/被编码为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上升n权利和零下降开始。由于还没有向上，我的bool B是false(如果出现向上，那么向下就不能出现在它之后，所以为了防止这种情况，我设置了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不是严格必要的，我们可以计算当前路径中的向上和向下，并计算出我们当前的高度，但这似乎是浪费。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

至于为什么您的解决方案不起作用？好吧，仅仅是你无法弄清楚这一事实就说明了你当前的解决方案开始变得多么复杂。当这种情况发生时，通常最好退后一步，重新思考你的方法，一步一步地写下你的程序应该做什么的明确规范，然后重新开始。