Permutation Operations in Rust
Introduction
To learn Rust I am porting my C# permutation library to Rust. I have learned quite a bit about Rust but am still not comfortable with it as it takes a bit of re-thinking how you code.
The source code for the following can be found at:
With no further ado, let’s get into the code.
Permutation Examples
A permutation is the order left to right that a set of objects can be arranged. Thus the set {1,2} has the permutations: {1,2}, {2,1}. The number of permutations for a given set of objects is n! where n is the number of objects (order) and ! is n factorial.
A permutation can be written as a two rows of numbers. The permutations of the order 2 set {1,2} can be written as:
We can express this in rust as:
Which produces the output:
While this works, it would be nice to aggerate permutation information in a Rust struct. The following source code creates a Permutation struct and implements the Display trait for it.
Run the following to produce the output:
While I love filling out struct declarations manually you probably don’t so let’s create a new method that takes two vectors:
Permutation Product
The permutation product is the composition of two permutations. The product is calculated from right to left. An example order 5 permutation product would be:
1. In the right array 1 maps to 3, then 3 maps to 5 in the left array. Thus the first value in the bottom row of the resultant permutation is 5.
2. In the right array 2 maps to 5, then 5 maps to 2 in the left array. Thus the second value in the bottom row of the resultant permutation is 2.
3. In the right array 3 maps to 1, then 1 maps to 3 in the left array. Thus the third value in the bottom row of the resultant permutation is 3.
4. In the right array 4 maps to 2, then 2 maps to 4 in the left array. Thus the fourth value in the bottom row of the resultant permutation is 4.
5. In the right array 5 maps to 4, then 4 maps to 1 in the left array. Thus the fifth value in the bottom row of the resultant permutation is 1.
And the resultant permutation is:
We will create a product method and implement the Mul trait (*) the source looks as follows:
Notice we added a new full_rep field to the Permutation struct and added a to_string method.
Running the above will produce the following output:
Permutation Identity
The permutation identity is any permutation that has the same top row as bottom row. (The top row is ordered). So for an order 4 permutation the identity is:
The identity method can be found in the perm_inverse.rs file below.
Permutation Inverse
A permutation inverse is a permutation that when the product is taken with another permutation returns the identity permutation. This is shown below for n = 3:
We will calculate the inverse permutation of order 4.
Exchange top row with bottom row
1 goes to 2 in new permutation
2 goes to 3 in new permutation
3 goes to 1 in new permutation
4 goes to 4 in new permutation
We are done.
We will create an inverse method. The source is below.
Running the above produces the following output:
Notice how taking the product of the two permutations produces the identity permutation.
Permutation Matrix
Permutation matrices are square matrices with a single 1 in each column and a single 1 in each row with zeros elsewhere. An example of a 3 x 3 permutation matrix:
We can convert from a permutation to a permutation matrix as follows:
Starting with zeroed matrix, Row 2, column 1 gets a 1
Row 1, column 2 gets a 1
Row 3, column 3 gets a 1
We are done
We will create a IntMatrix struct that will handle the duty as a permutation matrix (and other duties as well).
This method creates a permutation matrix from a permutation.
The full source is found below:
Running the above produces the following output:
Permutation Matrix Transpose
The transpose of a matrix is swapping the rows for columns in the matrix. An example for n = 3 is:
We implement the transpose method for IntMatrix
Permutation Matrix Inverse
The transpose of a permutation matrix is also it’s inverse.
The product of the a permutation matrix and it’s inverse is the identity:
We implement the inverse method for IntMatrix by taking it’s transpose.
Permutation Matrix Product
We implement the product method for IntMatrix.
The full source code is below:
Running above produces the following output:
Set of Permutations For Order n
The number of permutations for and ordered set is n! where n! is the factorial of n.
Thus the set [1, 2, 3] has the factorial n! = 6. Below are the six permutations.
Conclusion
Permutations are central to finite group theory. With the structs and methods above opens up pathways for exploring finite groups and subgroups of a very large order using Rust’s excellent concurrency methods and traits.
Porting my C# library to Rust has been challenging and fulfilling. I am sure my code needs a lot of polishing and hopefully I will reach my goal of writing good idiomatic Rust code.
Thanks for reading!!!