生成Schr der路径

Question

我想要生成schr der路径，从(0，0)到(2n，0)，没有峰，即没有上一步，然后是下一步。一些例子用于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-1upn权限开始，零downs.Since没有上升，但我的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并不是必要的，我们可以计算当前路径中的起伏，并计算出我们目前的高度，但这似乎是浪费。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

为什么你的解决方案不起作用？嗯，仅仅是你搞不懂这个事实就说明了你目前的解决方案是多么的复杂。当发生这种情况时，通常是一个好主意，后退一步，重新考虑您的方法，写下一个清晰的说明，说明您的程序应该一步一步地做什么，然后重新开始。