5
\$\begingroup\$

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?

\$\endgroup\$
2
  • \$\begingroup\$ 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"... \$\endgroup\$ – Vogel612 Mar 23 '16 at 23:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Eric Nielsen Mar 23 '16 at 23:55
5
\$\begingroup\$

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 unary operator.

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

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.