通过上行和下行来生成山脉的算法(java)

Question

我试图做经典问题来实现一个算法来打印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);

对我来说,它们具有相同的逻辑,就像在括号中一样,我们添加左括号'('每次都可以,但对于右括号')'我们只在右括号的数量大于左边时添加它.我们可以在这里做同样的捣蛋吗？我们添加'/'每次都可以,但对'''我们必须先计算'/'的数量...

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

如果有可能,你能帮助我重用这段代码吗？或者我应该从头开始另一个代码？

Answer 1

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

\n\n

\n

• 完全按原样使用它，并将生成的括号字符串集转换为山表示形式。

\n

• 更新它以直接生成山字符串。这是本答案中详细介绍的替代方案。

\n

\n\n

修改

\n\n

\n
• 更新递归函数以使用字符矩阵而不是字符数组。
\n

\n\n

这可以防止在构建解决方案时处理插入换行符的复杂情况。一旦解决方案完成，就会从此矩阵生成一个新字符串。

\n\n

\n
• 当解决方案完成时，从 char 矩阵生成一个字符串。
\n

\n\n

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

\n\n

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

\n\n

我们使用两个位置参数，表示为row和col，因为我们现在在二维中移动，它们与count旧代码中的参数相对应。和row表示col山线迄今为止引导我们的拐角处。col添加每个字符后，(column) 参数就会增加 1 。该row参数根据当前字符对应的是爬升还是下降而变化。

\n\n

\n
• 一旦我们添加的任何字符不再是当前研究的解决方案的一部分，就清除它们（用空格替换）。
\n

\n\n

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

\n\n

\n
• 在第一次递归调用之前初始化字符矩阵。
\n

\n\n

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

\n\n

Java代码

\n\n

下面是根据上述想法更新的 Java 代码。\n尽管列举了一些修改，但核心逻辑是相同的（递归结构相同 - 决定是否尝试添加上划线/下划线和终止标准不变）。

\n\n

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[][] str, int row, int col) {\n    if (leftRem < 0 || rightRem < leftRem) return; // invalid state\n\n    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */\n        StringBuilder sb = new StringBuilder();\n        for (int i = 0; i < str.length; i++) {\n            sb.append(String.copyValueOf(str[i]));\n            sb.append(System.lineSeparator());\n        }\n        list.add(sb.toString());\n    } else {\n        if (leftRem > 0) { // try a left paren, if there are some available\n            str[row][col] = '/';\n            addParen(list, leftRem - 1, rightRem, str, row - 1, col + 1);\n            str[row][col] = ' ';\n        }\n        if (rightRem > leftRem) { // try a right paren, if there\xe2\x80\x99s a matching left\n            str[row + 1][col] = '\\\\';\n            addParen(list, leftRem, rightRem - 1, str, row + 1, col + 1);\n            str[row + 1][col] = ' ';\n        }\n    }\n}\n\npublic static ArrayList<String> generateParens(int count) {\n    char[][] str = new char[count][count * 2];\n    for (int i = 0; i < str.length; i++) {\n        Arrays.fill(str[i], ' ');\n    }\n\n    ArrayList<String> list = new ArrayList<>();\n    addParen(list, count, count, str, count - 1, 0);\n    return list;\n}\n

\n\n

结果

\n\n

下面是输入为 3 时生成的山脉（即字符串的宽度为 6，因为我们有 3 次向上笔画和 3 次向下笔画）：

\n\n

  /\\  \n /  \\ \n/    \\\n\n\n /\\/\\ \n/    \\\n\n\n /\\   \n/  \\/\\\n\n\n   /\\ \n/\\/  \\\n\n\n\n/\\/\\/\\\n

\n\n

分析

\n\n

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

\n\n

(Q1)特定宽度有多少个有效字符串？

\n\n

(Q2) '/' 和 '\\' 的随机序列成为有效山的概率是多少？

\n\n

(Q3)包含相同数量的“/”和“\\”的随机序列成为有效山的概率是多少？

\n\n

下表针对不同的字符串长度回答了这些问题：

\n\n

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

\n

Answer 2

有趣的任务.计算可以并行完成.我将在"不回答"标签中显示代码,因为它与问题的语言标准不匹配(在并行数组处理语言Dyalog APL中进行,实际上它使用一行代码完成工作).请根据需要忽略该部分.但是,我会显示数据以及会发生什么.这很直观.

<不回答>

fn?{(?/(0?+\a-~a),(?÷2)=+/a)?a??(??2)??2*?} // Dynamic function, generates boolean matrix

format?{??(-1+(0.5×??)-+\?-0,¯1?~?)?¨'\/'[1+?]} // Dirty format function

</ not answer>

说参数(山脉的宽度)是n = 6.

步骤1.生成0到(2 ^ 6 - 1)之间的所有数字

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

第2步:抓住每个的2个底座(它们垂直在下面.0是最左边,然后是1,等等):

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

_{1.实际上,只需要生成从32到63的数字,因为我们只需要以1开头的2个基数.请参阅上面数据中的最顶行.顶部为零的列(数字)实际上甚至不应生成.)
2.实际上只需要生成偶数,因为最后一位必须为0.请参见上面数据中最下面的行.不应该真正生成底部的列(数字).)}

第3步:计算每列中的数量:

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6

并且做一个布尔标记= 1,其中总和是N的一半,即3(即,总共我们必须有像下坡一样多的上坡).这是我们的第一个布尔结果:

0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0

第4步:确保我们不要"低于地平线":

这意味着我们必须计算每列的累积总和,首先:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4
0 0 1 1 1 1 2 2 1 1 2 2 2 2 3 3 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 1 1 2 2 2 2 3 3 2 2 3 3 3 3 4 4 2 2 3 3 3 3 4 4 3 3 4 4 4 4 5 5
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6

然后对于移位的位(0变为1,反之亦然):

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0
5 5 4 4 4 4 3 3 4 4 3 3 3 3 2 2 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 4 4 3 3 3 3 2 2 3 3 2 2 2 2 1 1 3 3 2 2 2 2 1 1 2 2 1 1 1 1 0 0
6 5 5 4 5 4 4 3 5 4 4 3 4 3 3 2 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 5 4 4 3 4 3 3 2 4 3 3 2 3 2 2 1 4 3 3 2 3 2 2 1 3 2 2 1 2 1 1 0

然后从第1个减去第2个,然后得到

¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1  1  1  1  1  1  1  1  1 1 1 1 1 1 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0  2  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1  1  1  1  1  1  1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1  1  1 1 1 1 1 1 1  1  1 1 1 1 1 1 1 3 3 3 3 3 3 3 3
¯4 ¯4 ¯4 ¯4 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2 ¯2  0  0  0  0 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0  0  0  2  2  2  2 ¯2 ¯2 ¯2 ¯2  0  0  0  0  0  0 0 0 2 2 2 2  0  0 0 0 2 2 2 2 2 2 2 2 4 4 4 4
¯5 ¯5 ¯3 ¯3 ¯3 ¯3 ¯1 ¯1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯1 ¯1  1  1  1  1  3  3 ¯3 ¯3 ¯1 ¯1 ¯1 ¯1  1  1 ¯1 ¯1 1 1 1 1 3 3 ¯1 ¯1 1 1 1 1 3 3 1 1 3 3 3 3 5 5
¯6 ¯4 ¯4 ¯2 ¯4 ¯2 ¯2  0 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯2  0  0  2  0  2  2  4 ¯4 ¯2 ¯2  0 ¯2  0  0  2 ¯2  0 0 2 0 2 2 4 ¯2  0 0 2 0 2 2 4 0 2 2 4 2 4 4 6

并查看哪些列没有负值 ; 这是第二个布尔结果:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

第5步:从上面的两个布尔结果中获取AND:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0

这些是创建良好山脉的二进制数据列的位置.在列左下方,然后转换(为了便于阅读)到右边.1是uphills,2编辑:0是downhills:

 1 1 1 1 1  1 0 1 0 1 0 // 1 0 1 0 1 0 means /\/\/\
 0 0 1 1 1  1 0 1 1 0 0 
 1 1 0 0 1  1 1 0 0 1 0 
 0 1 0 1 0  1 1 0 1 0 0 // means //\/\\
 1 0 1 0 0  1 1 1 0 0 0 
 0 0 0 0 0              

这是一个很好的答案.如果需要,我们可以应用格式:

format [the boolean result]
????????????????????????????????????
?      ?      ?      ?      ?  /\  ?
?      ?   /\ ? /\   ? /\/\ ? /  \ ?
?/\/\/\?/\/  \?/  \/\?/    \?/    \?
????????????????????????????????????

稍大一点,n = 10:

DISP format¨?fn 10
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?    /\    ?
?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?     /\   ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?          ?     /\   ?          ?          ?          ?          ?          ?          ?          ?          ?     /\   ?   /\     ?   /\     ?   /\     ?   /\/\   ?   /  \   ?
?          ?          ?          ?          ?      /\  ?          ?          ?          ?          ?      /\  ?    /\    ?    /\    ?    /\/\  ?    /  \  ?          ?          ?          ?          ?      /\  ?          ?          ?          ?          ?      /\  ?    /\    ?    /\    ?    /\/\  ?    /  \  ?  /\      ?  /\      ?  /\      ?  /\      ?  /\  /\  ?  /\/\    ?  /\/\    ?  /\/\/\  ?  /\/  \  ?  /  \    ?  /  \    ?  /  \/\  ?  /    \  ?  /    \  ?
?          ?       /\ ?     /\   ?     /\/\ ?     /  \ ?   /\     ?   /\  /\ ?   /\/\   ?   /\/\/\ ?   /\/  \ ?   /  \   ?   /  \/\ ?   /    \ ?   /    \ ? /\       ? /\    /\ ? /\  /\   ? /\  /\/\ ? /\  /  \ ? /\/\     ? /\/\  /\ ? /\/\/\   ? /\/\/\/\ ? /\/\/  \ ? /\/  \   ? /\/  \/\ ? /\/    \ ? /\/    \ ? /  \     ? /  \  /\ ? /  \/\   ? /  \/\/\ ? /  \/  \ ? /    \   ? /    \/\ ? /      \ ? /      \ ? /    \   ? /    \/\ ? /      \ ? /      \ ? /      \ ?
?/\/\/\/\/\?/\/\/\/  \?/\/\/  \/\?/\/\/    \?/\/\/    \?/\/  \/\/\?/\/  \/  \?/\/    \/\?/\/      \?/\/      \?/\/    \/\?/\/      \?/\/      \?/\/      \?/  \/\/\/\?/  \/\/  \?/  \/  \/\?/  \/    \?/  \/    \?/    \/\/\?/    \/  \?/      \/\?/        \?/        \?/      \/\?/        \?/        \?/        \?/    \/\/\?/    \/  \?/      \/\?/        \?/        \?/      \/\?/        \?/        \?/        \?/      \/\?/        \?/        \?/        \?/        \?
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

编辑:当然,人们也可以在循环中完成所有这些.只需取一个数字,然后进行上面的检查(一个数= = n的一半,不低于地平线).如果检查失败则跳出.