Effective layout algorithm in java

Question

I am trying to write a method that will compute all permutations of a force set where order matters. I believe that they are called "arrangements." I mean:

{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 the set S, I have to generate every permutation of each subset of the power set S. Therefore, we first generate the power scheme, and then compare the permutation function to each set.

The problem is that it is very difficult - something like O (Σn! / K!) With k = 0..n.

I am wondering if there are any existing algorithms that do such things very efficiently (possibly a parallel implementation). Or perhaps even if there is a parallel power transmission algorithm and there is a parallel permutation algorithm, I can combine the two.

Thoughts?

Answer 1

The guava library provided by google contains various methods for rearranging collections.

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

Answer 2

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

C (3, 3) = 1 combination (abc)
C (3, 2) = 3 combinations (ab) (ac) (bc)
C (3, 1) = 3 combinations (a) (b) (c)

Now you create permutations for each combination.

Known algorithms for calculating 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 how to build appropriate algorithms.