Java 8 String Unique Permutations in Parallel

Is there a better way to do this Java 8 String Unique Permutations in Parallel

package com.bos;

import java.util.Date;
import java.util.Set;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.stream.IntStream;

public class StringPermutation {
    private static Set set = new ConcurrentSkipListSet();

    public static void permutation(String str) {
        permutation("", str);
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            set.add(prefix);
        } else {
            IntStream.range(0, n).parallel()
                    .forEach(i -> permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));
        }
    }

    public static void main(String[] args) {
        Date startDate = new Date();
        long startTime = System.nanoTime();
        System.out.println("Started at " + startDate);
        permutation("ferrao");
        set.stream().forEach(System.out::println);
        Date endDate = new Date();
        long totalTime = System.nanoTime() - startTime;
        System.out.println("Ended at " + endDate + " total time=" + totalTime + " nanosec");

    }
}

The presented way is not a functional solution. It uses streams but it relies on forEach, which is the imperative way of using a Stream.

To make it better, we need to think about what we really want to do. We want to build all the permutations of the characters in a String. That means we need to have a method permutations(String) that will return all the permutations. Using Java 8, we can return a Stream which will corresponds to the Stream of all the permutations.

To build those permutations, we can have a recursive algorithm:

• If the String is empty, there are no characters, so the only result is a Stream that contains the empty String. This is the base case.

• If the String is non-empty:

• we remove the first character, build all the permutations without it and then prepend the first character to all the results.

• then we remove the second character, build all the permutations without it and then prepend the second character to all the results.

• etc. until we hit the last character.

Using Java 8, this is an implementation:

public static Stream permutations(String str) {
    if (str.isEmpty()) {
        return Stream.of("");
    }
    return IntStream.range(0, str.length())
                .boxed()
                .flatMap(i ->
                  permutations(str.substring(0, i) + str.substring(i+1)).map(t -> str.charAt(i) + t)
                );
}

The base-case is handled by the if: when the String is empty, we return Stream.of(""): a Stream that contains only the empty String/

The main part is after: we create an IntStream over the indexes of the String. (Since there are unfortunately no flatMapToObj operation, we need to box each int into an Integer.) Then that's where the magic happens: for each index, we recurse by building all the permutations again, leaving the index i, and each of the result is mapped to prepend the character at index i. Since this recursive call returns a Stream, this result is flat mapped (with flatMap) to have a single Stream.

With this utility method, your code is then just

permutations("ferrao").forEach(System.out::println);

That brings also a big advantage: the method is returning a Stream, that is to say, the method does not actually perform the calculation. It is then up-to the caller to decide when to do it, if they want it to happen in parallel or not, and especially what the end container will be (a List, a Set, no container at all with just post-processing afterwards).

For example, to have it performed in parallel, you just need to do

permutations("ferrao").parallel().forEach(System.out::println);

StackExchange Code Review Q#120041, answer score: 3