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?

Crosswise

Maybe check this post out: stackoverflow.com/questions/1506078 – Wilfredowilfrid

possible duplicate of Fast permutation -> number -> permutation mapping algorithms – Ramify

I don't think it's a duplicate. I read that thread and it asks for something pretty different. The solutions are somewhat similar in theme but are certainly different enough to warrant separate threads. – Crosswise

If you want to compute all permutations than size of output is sum(n!/k!). It is possible to make it parallel in few ways: by size of sets, by first element(s) in sets. – Frodine

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.

Mahmud

Good answer, really handy for small collections, but I don't think that implementation scales when N grows. – Grafton

Answer 2

To do this you first generate the combinations for 1-n slots where n is the number of elements in the power set. For example, if you have 3 elements, then you will have:

C( 3, 3 ) = 1 combination (a b c)
C( 3, 2 ) = 3 combinations (a b) (a c) (b c)
C( 3, 1 ) = 3 combinations (a) (b) (c)

Now, you generate the permutations for each combination.

There are well known algorithms to calculate permutations and combinations. For example, Knuth's "The Art of Computer Programming", volume 4A, Sections 7.2.1.2 and 7.2.1.3, explain exactly how to construct the relevant algorithms.

Swash