c# - 生成施罗德路径

Question

我想生成从 (0, 0) 到 (2n, 0) 的施罗德路径没有峰值，即没有上升步紧接着下降步。一些示例适用于 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 ups n rights 和 0 downs 开始。因为没有 Up 但我的 bool B 是假的(如果出现 up 然后 down 不能跟随它，所以为了防止这种情况我放 B=true 来防止它.) 如果出现上升，则应该有相应的下降，并且 total 应该递增 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();
    }
}

请记住，将您的问题分解为更小的问题。所有困难的问题都可以通过解决更小更容易的问题来解决。这个辅助方法很难出错；很好，很难在简单的简短方法中编写错误。

现在，我们解决了更大的问题。我们不会使用迭代器 block ，因此移植更容易。我们将在此让步，使用可变列表来跟踪我们找到的所有有效路径。

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

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 和 downs 并计算出我们当前所处的高度，但这似乎浪费。 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

至于为什么您的解决方案不起作用？好吧，您无法弄清楚这一事实就说明了您当前的解决方案开始看起来有多么不必要的复杂性。当发生这种情况时，通常最好退后一步，重新考虑您的方法，写下您的程序应该逐步执行的明确规范，然后重新开始。