Efficient arrangement algorithm in java

Question

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?

Answer 1

The guava library provided by google contains different methods to permute collections.

See the javadoc of class com.google.common.collect.Collections2 here.