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

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?

• I think the definition of "permutation" you applied doesn't match the one generally thought of. As I understood you also include all shorter permutations of the array in the permutations? Usually you'd only talk about the permutations possible for the same length as the original array. Also some definitions even ignore offsets when seeing the array as a ring-buffer. Please clarify what exactly you mean when you say "permutation"... Commented Mar 23, 2016 at 23:41
• I mean as permutation of {1,2,3} are {2,3,1}, {3,2,1}, {3,1,2}, {1,3,2}, {2,1,3} and {1,2,3}. This is what above code returns. Commented Mar 23, 2016 at 23:55

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.

• Thank you, @vpn, makes sense! Where can I read more about permutations' natural ordering and constructing one from another? Commented Mar 24, 2016 at 0:12
• @EricNielsen It is all over the Internet. Just google for next permutation and pick anything.
– vnp
Commented Mar 24, 2016 at 0:15
• Right, got the Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. Commented Mar 24, 2016 at 0:18

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?