Menu
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?
828
5 Popular Sorting Algorithms in Java Merge Sort. Heap Sort. Insertion Sort. Selection Sort.
Algorithms in Java are static methods that can be used to perform various operations on collections. Since algorithms can be used on various collections, these are also known as generic algorithms. Let's see the implementation of different methods available in the collections framework.
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations. However, it uses a stable, adaptive, iterative implementation of mergesort algorithm for Array of Objects.
The guava library provided by google contains different methods to permute collections.
See the javadoc of class com.google.common.collect.Collections2 here.
93
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
