用上行和下行来生成山脉的算法（java） [英] Algorithm to generate mountain ranges with upstrokes and down-strokes (java)

问题描述

我尝试做经典问题来实现一个算法来打印n对括号的所有有效组合。我发现这个程序（运行正常）：

I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses. And I found this program (which works perfectly) :

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
It说：

Then, when I was searching for applications of Catalan Numbers, I found a very interresting application here : https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics It saids that:

我们可以使用加泰罗尼亚数字形成山脉，其中n次上行和n次击打都保持在原始线之上。山脉解释是山脉永远不会低于地平线

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

因此，我尝试重复使用上面的代码来实现解决方案这个问题。我不确定，但我认为我们可以重用这段代码，因为看起来它们具有相同的逻辑。
不幸的是，我尝试了很多东西用'/'和'\'替换括号但是我失败了。

Consequently, I tried to reuse the code above to implement a solution to this problem. I'm not sure, but I think that we can reuse this code since it seems that they have the same "logic". Unfortunately, I tried a lot of things to replace the brackets with '/' and '\' but I failed.

我试着做类似的事情那：

I tried to do something like that :

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

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

For me, they have the same logic, like in brackets, we add the left bracket '(' EACH time is possible, but for right bracket ')' we add it only if the number of right brackets is greater than the left. We can do the same raisoning here no? We add '/' EACH time is possible but for '\' we have to count the number of '/' before...

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

Which I found particularly difficult here is how can we insert the new lines here to have all the correct mountains?

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

Can you help me to reuse this code if it's possible? Or should I start another code from scratch?

推荐答案

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

There are more possible approaches for using the available parentheses generation code.

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

• Use it exactly as it is, and convert the resulting set of parentheses strings into mountain representations.

更新它以直接生成山脉弦乐。这是此答案中详述的替代方案。

Update it in order to directly generate the mountain strings. This is the alternative detailed in this answer.

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

• Update the recursive function to work with a char matrix instead of a char array.

这可以防止在构造解决方案时处理插入换行符的复杂性。解决方案完成后，将从此矩阵生成一个新字符串。

This prevents dealing with complications of inserting newlines while constructing the solution. A new string will be generated from this matrix once a solution is complete.

• 从char矩阵生成字符串解决方案完成时。

• Generate a string from the char matrix when a solution is complete.

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

Concatenate the strings associated to each row of the matrix, adding newlines after each row. Additionally (not implemented in the solution below), the trailing spaces of each row could be removed.

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

• Update the signature of the recursive function in order to accept now two position parameters, instead of a single one.

我们使用两个位置参数，表示行和 col ，因为我们现在正在进行两个维度，它们是<$ c的记者旧代码中的$ c> count 参数。 行和 col 表示到目前为止山脉引导我们的角落。我们添加的每个字符后， col （列）参数增加1。 行参数根据当前字符是对应于攀升还是下降而更改。

We use two position parameters, denoted row and col, as we are moving in two dimensions now, and they are the correspondents of the count parameter in the old code. The row and col indicate the corner where the mountain line has led us so far. The col (column) parameter increases by 1 after each character we add. The row parameter is changed according to whether the current character corresponds to climbing or descending.

• 清除（替换为空格）我们添加的任何字符，只要它们不再是当前调查解决方案的一部分。

• Clear (replace with space) any character that we have added as soon as they are not anymore being part of the currently investigated solution.

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

This was implicit in the 1D case, because we always ended up with strings of a fixed length and every new solution overwrote the previous ones. However, in the 2D case, if we don't clean up the path generated for a solution, we might see parts of it in the following solutions.

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

• Initialize the char matrix before the first recursive call.

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

The size of the matrix is count rows (because this is the maximum height of a solution that will be generated) and 2 * count columns (because this is the length when using count pairs of strokes). The matrix is initially filled with white spaces.

下面是根据更新的Java代码对上面的想法。
尽管列举了修改，核心逻辑是相同的（递归结构是相同的 - 决定是否尝试添加向上冲程/向下冲程和终止标准是没有改变）。

Below is the Java code that was updated according to the ideas above. Despite the modifications enumerated, the core logic is the same (the recursive structure is the same - the decision of whether to attempt adding an up-stroke / down-stroke and the termination criteria are not altered).

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个向下笔划）：

Results

Below are the resulting mountains when the input is 3 (i.e. the width of the string is 6, because we have 3 up-strokes and 3 down-strokes):

  /\  
 /  \ 
/    \


 /\/\ 
/    \


 /\   
/  \/\


   /\ 
/\/  \



/\/\/\

分析

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

Analysis

There are a few interesting questions that now can be answered about these strings.

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

(Q1) how many valid strings are there for a specific width?

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

(Q2) what is the probability of a random sequence of '/' and '\' to be a valid mountain?

（Q3）随机序列包含相等数量'/'和'\\的概率是多少'是一个有效的山？

(Q3) what is the probability of a random sequence containing equal number of '/' and '\' to be a valid mountain?

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

The table below answers to these questions for various string lengths:

 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%

这篇关于用上行和下行来生成山脉的算法（java）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！