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