ofPermutations(List<V> list)

[numeralnathan]

StreamEx has a method called ofPermutations(int length). This creates a StreamEx<int[]>.

I would like a method ofPermutations(List list) which returns StreamEx<List>. The returned stream has all of the permutations of the given list. However, the stream has distinct Lists (i.e. list1 != list2 for any given pair of Lists).

One could implement this with a mapping function. However, this results in allocating the int[] and the List.

[amaembo]

That was planned. The difficulty is that people would assume that if list contains equal elements, then permutations should not be duplicated. E.g. ofPermutations(asList(1,1,2)) would yield only 1,1,2, 1,2,1 and 2,1,1. That is, three elements instead of six. Also ofPermutations(asList(1,1,1)) should yield only one permutation. It's possible to implement but somewhat more difficult, especially if we want to support nice parallelization.

[numeralnathan]

I think if you document that duplicate Lists will be generated if duplicate elements are in the source list. Once could always do the following to eliminate duplicates...

ofPermutations(asList(1,1,2)).
   distinct()

[amaembo]

I guess, it would be much less efficient and take much more memory, compared to possible optimized implementation. Here some of possible solutions are listed.

[numeralnathan]

Here is a pseudo algorithm which can calculate the permutation given the lexicographical index. In other words, this can be used to split the Spliterator in O(1) time since all it requires is assigning an index range to each Spliterator. Here is some simple Python code. The Python code is a little slow since it computes the factorial each iteration of the loop instead of adjusting the factorial.