生成具有上冲程和下冲程的山脉的算法（java）

一尘不染

生成具有上冲程和下冲程的山脉的算法（java）

algorithm

我试图做一个经典的问题来实现一种算法，以打印n对括号的所有有效组合。我找到了这个程序（效果很好）：

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = ')';
            addParen(list, leftRem, rightRem - 1, str, count + 1);
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[] str = new char[count*2];
    ArrayList<String> list = new ArrayList<String>();
    addParen(list, count, count, str, 0);
    return list;
}

然后，当我搜索加泰罗尼亚语数字的应用程序时，我在这里找到了一个非常有趣的应用程序：https
://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics 它说：

我们可以使用加泰罗尼亚语数字形成n个上冲程和n个下冲程的山脉，这些山脉都保持在原始线以上。山脉的解释是山脉永远不会低于地平线

因此，我尝试重用上面的代码来实现此问题的解决方案。我不确定，但是我认为我们可以重用此代码，因为它们似乎具有相同的“逻辑”。不幸的是，我尝试了很多尝试将方括号替换为“
/”和“ \”，但失败了。

我试图做这样的事情：

    str[count] = '/';
    addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = '\\';
str[count+1] = '\n';
addParen(list, leftRem, rightRem - 1, str, count + 2);

对我来说，它们具有相同的逻辑，就像在方括号中一样，我们仅在左方括号的数量大于左方括号的情况下添加左方括号“（’每个时间是可能的，但对于右方括号’）’则将其添加。我们可以在这里做同样的事吗？我们添加了“
/”，每个时间都是可以的，但是对于“ \”，我们必须先计算“ /”的数量…

我在这里发现特别困难的是，如何在这里插入新行以拥有所有正确的山脉？

如果可以的话，您能帮我重用这段代码吗？还是应该从头开始另一个代码？

阅读 269

2020-07-28

共1个答案

一尘不染

还有更多使用可用括号生成代码的方法。

照原样使用它，然后将结果的括号字符串集转换为山表示形式。
更新它以直接生成山弦。这是此答案中详细介绍的替代方法。

修改项

更新递归函数以使用 char矩阵 而不是char数组。

这样可以避免在构造解决方案时插入换行符带来的麻烦。解决方案完成后，将从该矩阵中生成一个新字符串。

解决方案完成后， 从char矩阵 生成一个 字符串 。

连接与矩阵的每一行关联的字符串，并在每一行之后添加换行符。另外（在下面的解决方案中未实现），可以删除每行的尾随空格。

更新递归函数的签名，以便现在接受 两个位置参数 ，而不是单个 位置参数 。

我们使用两个位置参数，分别用row和表示col，因为我们现在在二维中移动，它们是count旧代码中该参数的对应物。在row和col指明山线使我们至今角落。在col我们添加每个字符后，（列）参数将增加1。该row参数是根据是否当前字符对应于攀登或下降变化。

*一旦我们添加的任何字符不再成为当前研究的解决方案的一部分，就将其 *清除（替换为空格）。

在一维情况下，这是隐式的，因为我们总是以固定长度的字符串结尾，并且每个新解决方案都覆盖了先前的解决方案。但是，在2D情况下，如果我们不清理为解决方案生成的路径，则可能会在以下解决方案中看到其中的一部分。

*在第一个递归调用之前 *初始化 char矩阵。

矩阵的大小是count行（因为这是将要生成的解决方案的最大高度）和2 * count列（因为这是使用count笔触对时的长度）。矩阵最初填充空白。

Java代码

以下是根据上述想法更新的Java代码。尽管列举了一些修改， 但是核心逻辑是相同的 （递归结构是相同的-
是否尝试增加上冲程/下冲程的决定以及终止标准都没有改变）。

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[][] str, int row, int col) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            sb.append(String.copyValueOf(str[i]));
            sb.append(System.lineSeparator());
        }
        list.add(sb.toString());
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[row][col] = '/';
            addParen(list, leftRem - 1, rightRem, str, row - 1, col + 1);
            str[row][col] = ' ';
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[row + 1][col] = '\\';
            addParen(list, leftRem, rightRem - 1, str, row + 1, col + 1);
            str[row + 1][col] = ' ';
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[][] str = new char[count][count * 2];
    for (int i = 0; i < str.length; i++) {
        Arrays.fill(str[i], ' ');
    }

    ArrayList<String> list = new ArrayList<>();
    addParen(list, count, count, str, count - 1, 0);
    return list;
}

结果

下面是输入为3（即字符串的宽度为6，因为我们有3个上冲程和3个下冲程）时产生的山脉：

  /\  
 /  \ 
/    \


 /\/\ 
/    \


 /\   
/  \/\


   /\ 
/\/  \



/\/\/\

分析

关于这些字符串，现在可以回答一些有趣的问题。

（Q1） 特定宽度有多少个有效字符串？

（Q2） 随机序列“ /”和“ \”成为有效山峰的概率是多少？

（Q3） 包含相等数量的“ /”和“ \”的随机序列成为有效山峰的概率是多少？

下表针对各种字符串长度回答了这些问题：

 Length           Valid           Total        Prob. Q2   Equal / and \        Prob. Q3
      2               1               4        25.0000%               2        50.0000%
      4               2              16        12.5000%               6        33.3333%
      6               5              64         7.8125%              20        25.0000%
      8              14             256         5.4688%              70        20.0000%
     10              42           1,024         4.1016%             252        16.6667%
     12             132           4,096         3.2227%             924        14.2857%
     14             429          16,384         2.6184%           3,432        12.5000%
     16           1,430          65,536         2.1820%          12,870        11.1111%
     18           4,862         262,144         1.8547%          48,620        10.0000%
     20          16,796       1,048,576         1.6018%         184,756         9.0909%
     22          58,786       4,194,304         1.4016%         705,432         8.3333%
     24         208,012      16,777,216         1.2398%       2,704,156         7.6923%
     26         742,900      67,108,864         1.1070%      10,400,600         7.1429%
     28       2,674,440     268,435,456         0.9963%      40,116,600         6.6667%
     30       9,694,845   1,073,741,824         0.9029%     155,117,520         6.2500%

2020-07-28