生成具有上冲程和下冲程的山脉的算法 (java)
Algorithm to generate mountain ranges with upstrokes and down-strokes (java)
我尝试做经典问题来实现一个算法来打印 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;
}
然后，当我在搜索 Catalan Numbers 的应用程序时，我在这里发现了一个非常有趣的应用程序：https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
它说：
We can use catalan numbers to form mountain ranges with n upstrokes and n down-strokes that all stay above the original line. The mountain range interpretation is that the mountains will never go below the horizon
因此，我尝试重用上面的代码来实现这个问题的解决方案。我不确定，但我认为我们可以重用这段代码，因为它们似乎具有相同的 "logic"。
不幸的是，我尝试了很多方法来用 '/' 和 '\' 替换括号，但都失败了。
我试过这样做：
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);
对我来说，他们有相同的逻辑，就像在括号中，我们添加左括号'(' EACH 时间是可能的，但是对于右括号')'我们只有在右括号的数量更大时才添加它比左边。我们可以在这里做同样的推理，不是吗？我们添加 '/' 每次都是可能的，但是对于 '\' 我们必须计算 '/' 之前的数量...
我发现这里特别困难的是我们如何在这里插入新行以获得所有正确的山脉？
如果可能的话，你能帮我重用这段代码吗？还是我应该从头开始编写另一个代码？
有更多方法可以使用可用的括号生成代码。
照原样使用，将生成的括号字符串集转换为山表示。
更新一下，直接生成山字串。这是此答案中详述的备选方案。
修改
- 更新递归函数以使用 char 矩阵 而不是 char 数组。
这可以防止在构建解决方案时处理插入换行符的复杂问题。解决方案完成后，将从该矩阵生成一个新字符串。
- 求解完成后，从字符矩阵生成字符串。
连接与矩阵的每一行关联的字符串，在每一行之后添加换行符。此外（未在下面的解决方案中实现），可以删除每行的尾随 spaces。
- 更新递归函数的签名以便现在接受两个位置参数，而不是一个。
我们使用两个位置参数，表示为row和col，因为我们现在在二维空间移动，它们对应于旧代码中的count参数. row 和 col 表示到目前为止山线将我们带到的拐角处。 col（列）参数在我们添加每个字符后增加 1。 row参数根据当前字符对应的是爬升还是下降来改变
- 清除（替换为space）我们添加的任何字符，一旦它们不再是当前调查解决方案的一部分。
这在 1D 情况下是隐含的，因为我们总是以固定长度的字符串结束，并且每个新解决方案都会覆盖以前的解决方案。但是，在 2D 情况下，如果我们不清理为解决方案生成的路径，我们可能会在以下解决方案中看到它的一部分。
- 在第一次递归调用之前初始化 char 矩阵。
矩阵的大小为 count 行（因为这是将要生成的解的最大高度）和 2 * count 列（因为这是使用 [=15 时的长度） =] 对笔划）。矩阵最初填充白色 spaces.
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)包含相等数量的'/'和'\'的随机序列是有效山的概率是多少？
下面的 table 针对不同的字符串长度回答了这些问题：
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%
有趣的任务。计算可以并行完成。我将在 "not answer" 标签内显示代码，因为它不符合问题的语言标准（用并行数组处理语言制作 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
< /不回答>
假设参数（山脉的宽度）是 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。请参见上面数据中的最下面一行。底部的列（数字）实际上什至不应该生成。）
第三步：计算每列的个数：
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
第四步：确保我们不去"below horizon":
这意味着我们必须计算每一列的累加和，首先：
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 ¯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
这些是创建好山的二进制数据列的位置。在 column-wise 下方向左，然后（为了便于阅读）向右转置。 1是上坡， 2 edit:0是下坡：
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
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ /\ │ /\ │ /\ │ /\ │ /\/\ │ / \ │
│ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ │ /\ │ /\ │ /\ /\ │ /\/\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │
│ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ /\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \/\ │ / \ │ / \ │ /\ │ /\ /\ │ /\ /\ │ /\ /\/\ │ /\ / \ │ /\/\ │ /\/\ /\ │ /\/\/\ │ /\/\/\/\ │ /\/\/ \ │ /\/ \ │ /\/ \/\ │ /\/ \ │ /\/ \ │ / \ │ / \ /\ │ / \/\ │ / \/\/\ │ / \/ \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │
│/\/\/\/\/\│/\/\/\/ \│/\/\/ \/\│/\/\/ \│/\/\/ \│/\/ \/\/\│/\/ \/ \│/\/ \/\│/\/ \│/\/ \│/\/ \/\│/\/ \│/\/ \│/\/ \│/ \/\/\/\│/ \/\/ \│/ \/ \/\│/ \/ \│/ \/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
编辑：当然也可以在一个循环中完成所有这些。每次只取一个数字，并进行上面的检查（1 的数量 == n 的一半，不低于 horizon）。有一个检查失败则跳出。
我尝试做经典问题来实现一个算法来打印 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;
}
然后，当我在搜索 Catalan Numbers 的应用程序时，我在这里发现了一个非常有趣的应用程序：https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics 它说：
We can use catalan numbers to form mountain ranges with n upstrokes and n down-strokes that all stay above the original line. The mountain range interpretation is that the mountains will never go below the horizon
因此，我尝试重用上面的代码来实现这个问题的解决方案。我不确定，但我认为我们可以重用这段代码，因为它们似乎具有相同的 "logic"。 不幸的是，我尝试了很多方法来用 '/' 和 '\' 替换括号，但都失败了。
我试过这样做：
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);
对我来说，他们有相同的逻辑，就像在括号中，我们添加左括号'(' EACH 时间是可能的，但是对于右括号')'我们只有在右括号的数量更大时才添加它比左边。我们可以在这里做同样的推理，不是吗？我们添加 '/' 每次都是可能的，但是对于 '\' 我们必须计算 '/' 之前的数量...
我发现这里特别困难的是我们如何在这里插入新行以获得所有正确的山脉？
如果可能的话，你能帮我重用这段代码吗？还是我应该从头开始编写另一个代码？
有更多方法可以使用可用的括号生成代码。
照原样使用，将生成的括号字符串集转换为山表示。
更新一下，直接生成山字串。这是此答案中详述的备选方案。
修改
- 更新递归函数以使用 char 矩阵 而不是 char 数组。
这可以防止在构建解决方案时处理插入换行符的复杂问题。解决方案完成后，将从该矩阵生成一个新字符串。
- 求解完成后，从字符矩阵生成字符串。
连接与矩阵的每一行关联的字符串，在每一行之后添加换行符。此外（未在下面的解决方案中实现），可以删除每行的尾随 spaces。
- 更新递归函数的签名以便现在接受两个位置参数，而不是一个。
我们使用两个位置参数，表示为row和col，因为我们现在在二维空间移动，它们对应于旧代码中的count参数. row 和 col 表示到目前为止山线将我们带到的拐角处。 col（列）参数在我们添加每个字符后增加 1。 row参数根据当前字符对应的是爬升还是下降来改变
- 清除（替换为space）我们添加的任何字符，一旦它们不再是当前调查解决方案的一部分。
这在 1D 情况下是隐含的，因为我们总是以固定长度的字符串结束，并且每个新解决方案都会覆盖以前的解决方案。但是，在 2D 情况下，如果我们不清理为解决方案生成的路径，我们可能会在以下解决方案中看到它的一部分。
- 在第一次递归调用之前初始化 char 矩阵。
矩阵的大小为 count 行（因为这是将要生成的解的最大高度）和 2 * count 列（因为这是使用 [=15 时的长度） =] 对笔划）。矩阵最初填充白色 spaces.
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)包含相等数量的'/'和'\'的随机序列是有效山的概率是多少？
下面的 table 针对不同的字符串长度回答了这些问题：
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%
有趣的任务。计算可以并行完成。我将在 "not answer" 标签内显示代码，因为它不符合问题的语言标准（用并行数组处理语言制作 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
< /不回答>
假设参数（山脉的宽度）是 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。请参见上面数据中的最下面一行。底部的列（数字）实际上什至不应该生成。）
第三步：计算每列的个数：
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
第四步：确保我们不去"below horizon":
这意味着我们必须计算每一列的累加和，首先：
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 ¯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
这些是创建好山的二进制数据列的位置。在 column-wise 下方向左，然后（为了便于阅读）向右转置。 1是上坡， 2 edit:0是下坡：
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
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ │ │ │ │ │ /\ │ │ │ │ │ │ │ │ │ /\ │ /\ │ /\ │ /\ │ /\/\ │ / \ │
│ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ │ │ │ │ /\ │ │ │ │ │ /\ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ │ /\ │ /\ │ /\ /\ │ /\/\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │
│ │ /\ │ /\ │ /\/\ │ / \ │ /\ │ /\ /\ │ /\/\ │ /\/\/\ │ /\/ \ │ / \ │ / \/\ │ / \ │ / \ │ /\ │ /\ /\ │ /\ /\ │ /\ /\/\ │ /\ / \ │ /\/\ │ /\/\ /\ │ /\/\/\ │ /\/\/\/\ │ /\/\/ \ │ /\/ \ │ /\/ \/\ │ /\/ \ │ /\/ \ │ / \ │ / \ /\ │ / \/\ │ / \/\/\ │ / \/ \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │ / \/\ │ / \ │ / \ │ / \ │
│/\/\/\/\/\│/\/\/\/ \│/\/\/ \/\│/\/\/ \│/\/\/ \│/\/ \/\/\│/\/ \/ \│/\/ \/\│/\/ \│/\/ \│/\/ \/\│/\/ \│/\/ \│/\/ \│/ \/\/\/\│/ \/\/ \│/ \/ \/\│/ \/ \│/ \/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\/\│/ \/ \│/ \/\│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \/\│/ \│/ \│/ \│/ \│
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
编辑：当然也可以在一个循环中完成所有这些。每次只取一个数字，并进行上面的检查（1 的数量 == n 的一半，不低于 horizon）。有一个检查失败则跳出。