在字符串中找到所有的 L-R 组合以遍历数据结构。

huangapple go评论73阅读模式
英文:

Finding all combinations of L-R in a String to traverse a datastrucure

问题

private List<String> createPaths(int len) {
    List<String> result = new ArrayList<>();
    
    if (len == 0) {
        result.add("");
        return result;
    }
    
    List<String> prevPaths = createPaths(len - 1);
    
    for (String path : prevPaths) {
        result.add(path + "L");
        result.add(path + "R");
    }
    
    return result;
}

注:这是用于生成指定长度的路径组合的 Java 方法。将此方法放入您的代码中,然后根据需要调用它,并传入所需的路径长度,即可获得相应长度的路径组合列表。

英文:

I want to create all possible variations to traverse a data structure. When I traverse i can either go left (L) or right (R). So my plan for this is to genereate all possible paths, before I traverse the data structure. Each character should serve as an instruction for traversing.

I need a method to generate the following:

private List&lt;String&gt; createPaths(int len){
            List&lt;String&gt; result = new ArrayList&lt;&gt;();
            // no clue how to generate them
            return result;
     }

for len = 1 the results should be:
{L,R}

for len = 2 the results should be:
{LL,LR,RR,RL}

for len = 3 the results should be:
{LLL,LLR,LRL,LRR,RLL,RLR,RRL,RRR}

I have already tried to solve it with the help of the binary numbers, but I failed.

答案1

得分: 3

"二进制数"是一个非常好的方法。
首先将您的路径视为二进制数。

所以对于 len=3,您会得到所有长度为 3 的二进制数。

这些数是从 0 到 7(十进制)。(= 2^3 = 8 个数)

因此编写一个循环从 0 到 (2^len - 1) 进行计数,
然后简单地将该数字转换为二进制表示,将 0 替换为 R,将 1 替换为 L(在所有前导 0 中始终获得长度为 len 的二进制表示)。

英文:

"binary numbers" are a very good approach.
So first think of your paths as binary numbers.
So for len=3 you get all binary numbers of length 3.

These are the numbers 0 to 7 (in decimal). (= 2^3 = 8 numbers)

So write a loop to count from 0 to (2^len -1)
Than simply take the number translate it to binary representation and replace 0 by R and 1 by L (all leading 0s to get always a binary representation of length len)

答案2

得分: 1

您的建议使用二进制数对我来说似乎可行。我们可以生成一个介于0和某个2的幂之间的固定宽度且填充为零的二进制数集合。然后,将所有的零替换为 L,将所有的一替换为 R

private List<String> createPaths(int len) {
    List<String> result = new ArrayList<>();

    String formatWidth = "%" + len + "s";

    for (int i = 0; i < Math.pow(2, len); ++i) {
        String val = String.format(formatWidth, Integer.toBinaryString(i))
            .replace(' ', '0')
            .replace("0", "L")
            .replace("1", "R");
        result.add(val);
    }

    return result;
}

System.out.println(createPaths(3));

这将打印出:

[LLL, LLR, LRL, LRR, RLL, RLR, RRL, RRR]
英文:

Your tip to use binary numbers actually seems workable to me. We can generate a collection of fixed width and zero padded binary numbers between 0 and some power of 2. Then, replace all zeroes with L and all ones with R.

private List&lt;String&gt; createPaths(int len) {
    List&lt;String&gt; result = new ArrayList&lt;&gt;();
    String formatWidth = &quot;%&quot; + len + &quot;s&quot;;

    for (int i=0; i &lt; Math.pow(2, len); ++i) {
         String val = String.format(formatWidth, Integer.toBinaryString(i))
             .replace(&#39; &#39;, &#39;0&#39;)
             .replace(&quot;0&quot;, &quot;L&quot;)
             .replace(&quot;1&quot;, &quot;R&quot;);
         result.add(val);
    }

    return result;
}

System.out.println(createPaths(3));

This prints:

[LLL, LLR, LRL, LRR, RLL, RLR, RRL, RRR]

huangapple
  • 本文由 发表于 2020年9月4日 17:42:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/63738688.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定