Permutation Operations in Rust

Bradrico Rigg
6 min readSep 8, 2021

--

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:

Source Code

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!!!

--

--