英文:
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<String> createPaths(int len){
List<String> result = new ArrayList<>();
// 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<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));
This prints:
[LLL, LLR, LRL, LRR, RLL, RLR, RRL, RRR]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论