Given an alphabet and a non-negative integer n, generate all strings over that alphabet with length from 0 to n. The exact-length version is the core subproblem.

For alphabet "abc" and exact length 2, the result is:

1
aa ab ac ba bb bc ca cb cc

§Java Implementation

The Java version uses depth-first search with backtracking. It follows one candidate string to the requested length before returning to explore the next branch. The up-to-length variant repeats the same fixed-length search across the requested range.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.ArrayList;

class gen_str {
    static void dfs(int level, StringBuilder sb, ArrayList<String> acc, int len, char[] alphabet) {
        if (level == len) {
            acc.add(sb.toString());
            return;
        }

        for (var c : alphabet) {
            sb.append(c);
            dfs(level + 1, sb, acc, len, alphabet);
            sb.deleteCharAt(sb.length()-1);
        }
    }

    static ArrayList<String> gen_str_with_len(int len, String alphabet) {
        ArrayList<String> acc = new ArrayList<>();
        dfs(0, new StringBuilder(), acc, len, alphabet.toCharArray());
        return acc;
    }

    static ArrayList<String> gen_str_up_to_len(int len, String alphabet) {
        ArrayList<String> acc = new ArrayList<>();
        for (int i = 0; i <= len; i++) {
            var tmp_acc = gen_str_with_len(i, alphabet);
            acc.addAll(tmp_acc);
        }
        return acc;
    }

    void main() {
        String alphabet = "abc";
        int len = 3;

        ArrayList<String> acc = gen_str_up_to_len(len, alphabet);

        System.out.println(acc);
        System.out.println(acc.size());
    }
}

§Haskell Implementation

The Haskell version expresses the same enumeration as breadth-first expansion. It works level by level, expanding all partial candidates of the current length before moving to the next length. This contrasts with the Java implementation, which follows one branch at a time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- generate strings with given length from the alphabet
gen_len :: Int -> [Char] -> [String]
gen_len n alphabet = gen_len' n [""]
  where
    gen_len' 0 acc = map reverse acc
    gen_len' n acc = gen_len' (n-1)
      $ concatMap (\es -> [(e:es) | e <- alphabet]) acc

-- generate strings with <= length from the alphabet
gen_up_to_len :: Int -> [Char] -> [String]
gen_up_to_len n alphabet =
  concat [gen_len i alphabet | i <- [0..n]]

main = do
  print $ gen_len 2 "abc"
  print $ gen_up_to_len 2 "abc"
  print $ length $ gen_up_to_len 3 "abc"