Java 8 Stream to produce all permutations of an array using recursion

Question

I want to write a class that returns a Stream of permutations of an int[].

public class Permutations {
    public static Stream<int[]> of(int[] array) {
        return permute(array, array.length);
    }
    public static Stream<int[]> permute(int[] array, int n) {
        if (n == 1) {
            return Stream.of(Arrays.copyOf(array, array.length));
        } else {
            Stream tmp = Stream.empty();
            for (int i = 0; i < n; i++) {
                swap(array, i, n - 1);
                tmp = Stream.concat(permute(array, n - 1), tmp);
                swap(array, i, n - 1);
            }
            return tmp;
        }
    }
    private static void swap(int[] a, int i, int j) {
        if (i != j) {
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        }
    }
}

Problem with my solution is that it is nesting a lot of Streams with concat, many of them being just empty ones. Another issue is that it creates all permutations before returning the Stream, so it not really streaming... :- )

I saw Minborg's solution, but I wanted to make something simpler, here based on Sedgewick and Wayne's algorithm.

Can above code be improved?

Answer 1

Not a review, but an extended comment:

I strongly advise against recursion here. The permutations have a natural (lexicographic) ordering, and given a permutation it is easy to construct a next one.

This hints that to achieve true streaming: implement nextPermutation() method, and pass it to Stream.iterate() as an UnaryOperator.

Answer 2

I would suggest not dropping the Stream type parameter on the tmp variable.

A general way to do "loop within a loop" operations with Streams is to create a mapping function that takes a Stream element and returns a Stream of the values produced in the inner loop, and using it to merging the inner Stream into the results using Stream.flatMap() (or IntStream.flatMap in your case). I believe the flatMap function can be recursive, creating streams within streams, each flatMapping its results into its parent stream

One hurdle will be that you modify the collection of data during the streaming, which is a no-no--perhaps you can copy the array before swapping?