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

user_2605902 0
Viewed 62

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.

permutation algorithm java
2 Answers

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

user_19212730

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]
user_18632290
Related