Question

Create strings with predefined conditions

Is there anything in java that does the opposite of regular expressions?

My task is: given a defined total length for a string and each position can only consist of predefined specific characters, generate all possible strings.

To give an example: I want to create all stings of length 3 where the positions are defined as

[ABC][123][XYZ]

This means that the first position can only be A, B or C, the second position one of the numbers 1 to 3 and so on. Valid strings would therefore be

A1X 
A1Y 
A1Z 
A2X 
A2Y 
A2Z 
...
... 
C3Z 

For the length three I can of course use a nested loop. My problem is I don't know in advance how long the string has to be or how many valid characters each position has. Any ideas?

Code for length 3 and each position 3 possible chars:

public static void main(String[] args) {
    String[] first  = {"A", "B", "C"};
    String[] second = {"1", "2", "3"};
    String[] third  = {"X", "Y", "Z"};

    List<String> result = createStrings(first, second, third);

    result.forEach(System.out::println);
}

static List<String> createStrings(String[] ... strs) {
    String[] first  = strs[0];
    String[] second = strs[1];
    String[] third  = strs[2];

    List<String> result = new ArrayList<>();
    for (int i = 0; i < first.length; i++) {
        for (int j = 0; j < second.length; j++) {
            for (int k = 0; k < third.length; k++) {
                result.add(first[i] + second[j] + third[k]);
            }
        }
    }
    return result;
}

I need something flexible, which works for all inputs. Or a way to dynamically create a nested loop depending on strs.length which defines how many loops I need.

 5  93  5
1 Jan 1970

Solution

 5

You can use recursion:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] first = { "A", "B", "C" };
        String[] second = { "1", "2", "3" };
        String[] third = { "X", "Y", "Z" };
        String[] fourth = { "K", "L", "M" };
        String[] fifth = { "7", "8", "9" };

        List<String> result = createStrings(first, second, third, fourth, fifth);

        result.forEach(System.out::println);
    }

    static List<String> createStrings(String[]... strs) {
        List<String> res = new ArrayList<>();
        getStrings(0, "", res, strs);
        return res;
    }

    static void getStrings(int level, String curr, List<String> res, String[]... strs) {
        if (level == strs.length) {
            res.add(curr);
            return;
        }

        for (String ch : strs[level]) {
            getStrings(level + 1, curr + ch, res, strs);
        }
    }
}

Prints

A1XK7
A1XK8
A1XK9
A1XL7
A1XL8
A1XL9
A1XM7
...

C3ZK9
C3ZL7
C3ZL8
C3ZL9
C3ZM7
C3ZM8
C3ZM9

Tree level construction of a string:


                              ""
                            /  |  \
                          A    B    C
                         /|\  /|\  /|\
                       1 2 3 1 2 3 1 2 3
                      /|\ /|\ /|\ /|\ /|\
                     X Y Z X Y Z X Y Z X Y Z
                    /|\/|\/|\/|\/|\/|\/|\/|\
                   K L M K L M K L M K L M K L M
                  /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\
                 ... ... ... ... ... ... ... ... 
  • In this example, we have five levels. We want to generate all possible combinations of characters by recursively concatenating each character (from each level) using the current array (strs[level]) and then move to the next level.

  • Initially, we call createStrings() with all five arrays, which calls getStrings(0, "", res, strs).

Here are the recursion stacks:

First Level (level = 0):

  • Calls with curr = "A", curr = "B", curr = "C"

Second Level (level = 1):

  • For curr = "A": Calls with curr = "A1", curr = "A2", curr = "A3"
  • For curr = "B": Calls with curr = "B1", curr = "B2", curr = "B3"
  • For curr = "C": Calls with curr = "C1", curr = "C2", curr = "C3"

Third Level (level = 2):

  • For curr = "A1": Calls with curr = "A1X", curr = "A1Y", curr = "A1Z"
  • For curr = "A2": Calls with curr = "A2X", curr = "A2Y", curr = "A2Z"
  • For curr = "A3": Calls with curr = "A3X", curr = "A3Y", curr = "A3Z"
  • ...

Fourth Level (level = 3):

  • For curr = "A1X": Calls with curr = "A1XK", curr = "A1XL", curr = "A1XM"
  • For curr = "A1Y": Calls with curr = "A1YK", curr = "A1YL", curr = "A1YM"
  • For curr = "A1Z": Calls with curr = "A1ZK", curr = "A1ZL", curr = "A1ZM"
  • ...

Fifth Level (level = 4):

  • For curr = "A1XK": Calls with curr = "A1XK7", curr = "A1XK8", curr = "A1XK9"
  • For curr = "A1XL": Calls with curr = "A1XL7", curr = "A1XL8", curr = "A1XL9"
  • For curr = "A1XM": Calls with curr = "A1XM7", curr = "A1XM8", curr = "A1XM9"

...


Let's trace one path through the recursion stack:

  • First call: getStrings(0, "", res, strs), calls getStrings(1, "A", res, strs);
  • Second call: getStrings(1, "A", res, strs), calls getStrings(2, "A1", res, strs);
  • Third call: getStrings(2, "A1", res, strs), calls getStrings(3, "A1X", res, strs);
  • Fourth call: getStrings(3, "A1X", res, strs), calls getStrings(4, "A1XK", res, strs);
  • Fifth call: getStrings(4, "A1XK", res, strs), calls getStrings(5, "A1XK7", res, strs); and
  • Base case: getStrings(5, "A1XK7", res, strs), adds "A1XK7" to the res.
2024-07-07
user24714692

Solution

 3

One way to list all the combinations of multiple character arrays is to create a counter that counts through the possibilities.

The code creates an int array of digits and an int array of limits. We count through the array of digits until the limit in each position is hit. Then the digit is reset to zero and the next digit is incremented.

Like this (assuming each character array has three possibilities):

000
001
002
010
011
...

Here's the complete runnable code.

import java.util.ArrayList;
import java.util.List;

public class CreateStrings {

    public static void main(String[] args) {
        String[] first = { "A", "B", "C" };
        String[] second = { "1", "2", "3", "4" };
        String[] third = { "X", "Y", "Z" };

        List<String> result = createStrings(first, second, third);
        result.forEach(System.out::println);
    }

    private static List<String> createStrings(String[]... strs) {
        List<String> strings = new ArrayList<>();
        int[] digits = new int[strs.length];
        int[] limits = new int[strs.length];
        for (int index = 0; index < strs.length; index++) {
            limits[index] = strs[index].length;
        }

        boolean inProcess = true;
        while (inProcess) {
            String s = "";
            for (int index = 0; index < digits.length; index++) {
                s += strs[index][digits[index]];
            }
//          System.out.println(s);
            strings.add(s);

            for (int index = digits.length - 1; index >= 0; index--) {
                digits[index]++;
                if (digits[index] >= limits[index]) {
                    if (index == 0) {
                        inProcess = false;
                    }
                    digits[index] = 0;
                } else {
                    break;
                }
            }
        }

        return strings;
    }

}
2024-07-07
Gilbert Le Blanc