Menu
In my experience in programming, I often face with different tasks related to permutation group: enumerate all possible products of given permutations or just count them, test whether one permutation can be represented as a combination of given ones, find a subgroup in a given group etc. I suppose that these problems are classic of a computer science and arise in various fields of programming. Currently, in our project we use our own primitive implementation of PermutationGroup based on a simplest version of Schreier-Sims algorithm, but it is very limited. I know about various C++ and Python libraries, but is there any Java library which have an efficient implementation of PermutationGroup and related topics?
Thanks, Stanislav.
800
We use the size() method to get the number of elements in the list. We set a constant value 3 to r, i.e., the number of items taken for the Permutation. After that, we use the permutation formula, i.e., fact(n)/fact(n-r) and store the result into the result variable. At last, we show the final result to the users.
In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself).
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.
Permutation and Combination in Java In mathematics, Permutation and Combination are two important concepts. Permutation is the different arrangements of the set elements. The arrangements can be made by taking one element at a time, some element at a time and all elements at a time.
is called a permutation. The number of elements in finite set G is called the degree of Permutation. Let G have n elements then P n is called set of all permutation of degree n. P n is also called the Symmetric group of degree n. P n is also denoted by S n. Case 3: Let G= { 1, 2, 3 } elements then permutation are 3!=6.
The function is next_permutation (a.begin (), a.end ()). It is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range).
The algorithm generates the permutations by shuffling the array. For shuffling, the Java Collections class provides the shuffle () method. The shuffle () method randomly permutates the specified List using a default source of randomness. It traverses the list in a backward (from the last element to the second element) direction.
There is implementation of PermutationGroup and related algorithms in Java in Redberry computer algebra system (which is available from Maven Central as cc.redberry.core). It includes basic algorithms for representing permutation groups in computer (based on base and strong generating set and Schreier-Sims algorithm) and backtrack search algorithms for some types of subgroups (set stabilizers, centralizers etc.). The implementation provides all requested features: enumerating group elements, membership testing, calculation of group order (total number of permutations) and many more.
The following example taken from Redbery JavaDoc page highlights some PermutationGroup functionality:
//permutation in cycle notation
Permutation p1 = Permutations.createPermutation(new int[][]{{0, 9, 3}, {5, 8, 6}, {7, 11, 12}});
//permutation in one-line notation
Permutation p2 = Permutations.createPermutation(2, 0, 1, 8, 3, 5, 7, 11, 4, 12, 9, 6, 10);
//Construct permutation group
PermutationGroup pg = PermutationGroup.createPermutationGroup(p1, p2);
//this group is transitive
assert pg.isTransitive();
//its order = 5616
System.out.println(pg.order());
//Create alternating group Alt(13)
PermutationGroup alt13 = PermutationGroup.alternatingGroup(13);
//its order = 3113510400
System.out.println(alt13.order());
assert alt13.containsSubgroup(pg);
//Direct product of two groups
PermutationGroup pp = pg.directProduct(PermutationGroup.symmetricGroup(8));
//Setwise stabilizer
PermutationGroup sw = pp.setwiseStabilizer(1, 2, 3, 9, 10, 11, 12, 3, 14, 15, 16, 17, 18);
assert pp.containsSubgroup(sw);
//its order = 17280
System.out.println(sw.order());
//Center of this stabilizer
PermutationGroup center = sw.center();
//it is abelian group
assert center.isAbelian();
//generators of center
//[+{}, +{{19, 20}}, +{{2, 10}, {3, 9}, {6, 8}, {11, 12}}]
System.out.println(center.generators());
More about PermutationGroup functionality can be found at Redberry JavaDoc page.
There is also a nice Groovy interface to Java classes, examples can be found here.
126
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