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?

Maybe check this post out: http://stackoverflow.com/questions/1506078 — squiguy, Jun 18 '12 at 18:00
possible duplicate of [Fast permutation -> number -> permutation mapping algorithms](http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms) — Makoto, Jun 18 '12 at 21:55
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. — rhombidodecahedron, Jun 18 '12 at 22:03
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. — Ante, Jun 19 '12 at 14:30

score 1 · Accepted Answer · answered Jun 19 '12 at 15:31

1

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

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

answered Jun 19 '12 at 15:31

luchoct

419
3
6

Good answer, really handy for small collections, but I don't think that implementation scales when N grows. – Guido Oct 13 '12 at 10:24

score 0 · Answer 2 · answered Sep 20 '12 at 22:34

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.

Efficient arrangement algorithm in java

2 Answers2