permutation of words using java stream

Question

I'm trying to generate all possible words of length 0 to 4 with letters a to z and A to Z. This is what I have using Java stream

    static String[] letters
            = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
    letters[0] = "";

    static final int CAPACITY = 1 + 52 + 52*52 + 52*52*52 + 52*52*52*52;

    static List words
        = Arrays.stream(LETTERS)
            .flatMap(word -> Arrays.stream(LETTERS).map(word::concat))
            .flatMap(word -> Arrays.stream(LETTERS).map(word::concat))
            .flatMap(word -> Arrays.stream(LETTERS).map(word::concat))
            .distinct()
            .collect(Collectors.toCollection(() -> new ArrayList<>(CAPACITY)));

Is there another solution where I don't have to use distinct()? I know I could do something like:

    String[] letters
            = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
    List words = new ArrayList<>();
    words.add("");
    for(String letter1 : letters) {
        words.add(letter1);
        for(String letter2 : letters) {
            words.add(letter1 + letter2)
            for(String letter3 : letters) {
                words.add(letter1 + letter2 + letter3);
                for(String letter4 : letters) {
                    words.add(letter1 + letter2 + letter3 + letter4);
                }
            }
        }
    }

But I want to do it using Java stream.

(Edit) After your suggestions:

public static List generateWords(int maxLength, String[] 
    letters) {
    if (letters.length == 0)
        return Arrays.asList("");

    int capacity = IntStream.rangeClosed(0, maxLength)
            .map(i -> (int) Math.pow(letters.length, i))
            .sum();

    return IntStream.range(0, capacity)
            .mapToObj(i -> map(i, letters))
            .collect(Collectors.toCollection(() -> new ArrayList<>(capacity)));
}

private static String map(int index, String[] letters) {
    if(index == 0) return "";
    return map((index - 1) / letters.length, letters)
            + letters[(index - 1) % letters.length];
}

Malte Hartwig · Accepted Answer

Thanks for the cool question, really nice one!

The reason you need the distinct is the empty string, i.e. the words that are less than 4 characters long. For example, ...a, ..a., .a.., and a... all result in a, and you need the distinct to remove them. We should find a way around this, as distinct might mean a lot of comparisons, which might have quite an impact at such numbers.

It is not that hard to prevent creating duplicates: Do not add "" to your letters.

Looking at your own approach, if you only stream the actual characters, and add "" only after each flatMap, you get exactly what you need:

Condsider letters = {a, b}, maxLength = 2

Start with Stream.of("")

1st flatMap: [a, b]
add "": [, a, b]

2nd flatMap: [a, b, aa, ab, ba, bb]
add "": [, a, b, aa, ab, ba, bb]

Here is a nice method that does exactly that:

private static List maxWords(int maxLength, String[] letters)
{
    if (letters.length == 0)
    {
        return Arrays.asList("");
    }

    Stream s = Stream.of("");
    int[] capacity = { 1 };

    for (int i = 0; i < maxLength; i++)
    {
        s = Stream.concat(Stream.of(""), s.flatMap(word -> Arrays.stream(letters).map(word::concat)));
        capacity[0] = capacity[0] + (int) Math.pow(letters.length, i + 1);
    }

    return s.collect(Collectors.toCollection(() -> new ArrayList<>(capacity[0])));
}

This alternative is based on Aaron's idea, which I like even more. We first enumerate from 0 to capacity-1, and then map each number to its corresponding word. I strongly recommend watching this video about the Library of Babel (from minute 17) for an explanation if you are interested.

private static List maxWords2(int maxLength, String[] letters)
{
    if (letters.length == 0)
    {
        return Arrays.asList("");
    }

    int capacity = IntStream.rangeClosed(0, maxLength)
                            .map(length -> (int) Math.pow(letters.length, length))
                            .sum();

    return IntStream.range(0, capacity).mapToObj(i -> {
        StringBuilder s = new StringBuilder();
        while (i > 0)
        {
            i--;
            s.append(letters[i % letters.length]);
            i /= letters.length;
        }
        return s.reverse().toString();
    }).collect(Collectors.toCollection(() -> new ArrayList<>(capacity)));
}

permutation of words using java stream

Answers (2)

Related Questions