Создание путей Шредера

Question

Я хочу генерировать дорожки schröder от (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 прав и ноль downs.Since нет Up еще мой bool B является ложным (если приходит вверх, то вниз не может прийти после него, поэтому, чтобы предотвратить это, я положил B ​​= true, который предотвращает это .) Если приходит всплывающее окно, то должно быть соответствующее уменьшение, а сумма должна быть увеличена на единицу. Если это так, то сумма должна быть увеличена на 2. Мой алгоритм в целом работает так, но я не смог получить правильный результат с этой реализацией.

Answer 1

Исходное решение не адаптировалось к потребностям OP, поскольку оно было слишком сложным для переноса на javascript, и целью было показать лучшие методы решения этих проблем больше, чем просто решить это, в частности.

Но в духе использования неизменных типов для решения алгоритмов пути мы все еще можем сделать это гораздо проще: мы будем использовать string.

Ok, как всегда, позволяет создать инфраструктуру: инструменты, которые делают нашу жизнь проще:

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(); 
    } 
} 

Помните, расщеплять ваши проблемы меньшие проблемы. Все трудные проблемы можно решить, решая более мелкие проблемы. Этот вспомогательный метод трудно ошибиться; Это хорошо, его трудно написать ошибку внутри простых коротких методов.

И теперь мы решаем большую проблему. Мы не будем использовать блоки итераторов, поэтому перенос будет проще. Мы уступим здесь, используя измененный список, чтобы отслеживать все допустимые пути, которые мы находим.

Нашего рекурсивное решение заключается в следующем:

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 

Относительно того, почему ваше решение не работает?Ну, только тот факт, что вы не можете понять это, говорит о том, как все ненужное осложняет ваше текущее решение. Когда это происходит, обычно рекомендуется вернуться назад, переосмыслить свой подход, записать четкую спецификацию того, что ваша программа должна делать шаг за шагом, и начать все заново.