I'm trying to write a method that will compute all permutations of a power set where order matters. I believe these are called "arrangements." What I mean by this is:
{a} -> {{a}, {}}
{a,b} -> {{a,b}, {b,a}, {a}, {b}, {}}
{a,b,c} -> {{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}, {a,b}, {a,c}, {b,a}, {b,c}, {c,a}, {c,b}, {a}, {b}, {c}, {}}
etc. My impression is that, given a set S, I should generate every permutation of every subset of the powerset of S. So first generate the powerset, then map a permutation function onto each set.
The problem is that this is immensely complex -- something like O(∑n!/k!) with k=0..n.
I'm wondering if there are any existing algorithms that do this sort of thing very efficiently (perhaps a parallel implementation). Or perhaps even if a parallel powerset algorithm exists and a parallel permutation algorithm exists, I can combine the two.
Thoughts?
The guava library provided by google contains different methods to permute collections.
See the javadoc of class com.google.common.collect.Collections2 here.