### 5 stable releases

Uses old Rust 2015

3.0.0 | Nov 11, 2017 |
---|---|

2.0.0 | Nov 11, 2017 |

1.1.2 | Nov 8, 2017 |

1.1.0 | Sep 3, 2017 |

1.0.0 | Aug 21, 2017 |

#**1800** in Algorithms

**MIT**license

44KB

816 lines

# permutation-rs

Rust code to solve permutation puzzles.

## Tutorial

In this tutorial we will learn to solve the brainbow. Let's start by creating a new project.

`cargo`` new`` --`bin` --`name brainbow solve-brainbow

Open the

and add a dependency for `Cargo.toml`

.`permutation.rs`

`permutation-rs = "1.1.0"
`

open

and announce the `src/main.rs`

.`permutation-rs`

`#``[``macro_use``]`
`extern` `crate` permutation_rs`;`

Next we are going to import everything to start working with the brainbow group.

`use` `std``::``collections``::`HashMap`;`
`use` `permutation_rs``::``group``::``{`Group`,` GroupElement`,` Morphism`}``;`
`use` `permutation_rs``::``group``::``special``::`SLPPermutation`;`
`use` `permutation_rs``::``group``::``tree``::``SLP``;`
`use` `permutation_rs``::``group``::``free``::`Word`;`
`use` `permutation_rs``::``group``::``permutation``::`Permutation`;`

We are going to focus on creating the corresponding brainbow group. We introduce a function for that.

`fn` `brainbow``(``)`` ``->` `Group``<``u64`, SLPPermutation`>` `{`
`let` transposition `=` `SLPPermutation``::`new`(`
`SLP``::`Generator`(``0``)``,`
`permute!``(`
`0``,` `0``,`
`1``,` `1``,`
`2``,` `2``,`
`3``,` `5``,`
`4``,` `4``,`
`5``,` `3`
`)``,`
`)``;`
`let` rotation `=` `SLPPermutation``::`new`(`
`SLP``::`Generator`(``1``)``,`
`permute!``(`
`0``,` `1``,`
`1``,` `2``,`
`2``,` `3``,`
`3``,` `4``,`
`4``,` `5``,`
`5``,` `0`
`)``,`
`)``;`
`let` gset`:` `Vec``<``u64``>` `=` `vec!``(``0``,` `1``,` `2``,` `3``,` `4``,` `5``)``;`
`let` generators `=` `vec!``(`transposition`,` rotation`)``;`
`Group``::`new`(`gset`,` generators`)`
`}`

Let's talk about what is going on here. From the signature we learn that we are
returning a

. The group elements are made up of
`Group <u64, SLPPermutation>`

`SLPPermutation`

and act upon `u64`

. An `SLPPermutation`

is the combination of a
`SLP`

and a `Permutation`

with some extra bookkeeping. We will get into what
this all means.In the function we then define two generators. You can see how an

is composed of a `SLPPermutation`

and a `SLP`

. Notice that we
create a `Permutation`

with the `Permutation`

macro. For example`permute!`

`permute!``(`
`0``,` `0``,`
`1``,` `1``,`
`2``,` `2``,`
`3``,` `5``,`
`4``,` `4``,`
`5``,` `3`
`)`

corresponds to the following permutation in disjoint cycle notation

. We
create a `(``3` `5``)`

by listing the domain elements that our group is acting upon,
and we also gather the generators of our group. From these we create our actual
group.`gset`

With the possibility of creating a group we should start to make use of it. In
the main function call the

function and assign it to a variable.`brainbow`

`let` group `=` `brainbow``(``)``;`

Now it is time to scramble up the brainbow and create a corresponding group element to examine.

`let` element `=` `SLPPermutation``::`new`(`
`SLP``::`Identity`,`
`permute!``(`
`0``,` `1``,`
`1``,` `0``,`
`2``,` `5``,`
`3``,` `4``,`
`4``,` `3``,`
`5``,` `2`
`)``,`
`)``;`

We are going to use our

to strip this element. This determines a couple
of things. It can tell use if this element is in the group. An other thing which
we will learn is a word that will solve the scrambled brainbow if the element is
in the group.`group`

`let` stripped `=` group`.``strip``(`element`)``;`

In order to now a sequence of moves that solves this instance of the brainbow
puzzle, we need a

. A `Morphism`

tells how `Morphism`

elements should map
into instruction.`SLP`

`let` morphism `=` `morphism!``(``0``,` `'`t`'``,` `1``,` `'`r`'``)``;`

Let's use it to solve our puzzle.

`if` stripped`.`element`.``1.``is_identity``(``)` `{`
`println!``(``"``{}``"``,` stripped`.``transform``(``&`morphism`)``.``inverse``(``)``)``;`
`}` `else` `{`
`println!``(``"`Not solveable`"``)``;`
`}`

Running this program will output

`t^1r^4t^-1r^-1t^-1r^1t^1r^1
`

Which solves our puzzle.

## What is an SLPPermutation?

We said before that an

is the combination of a `SLPPermutation`

and a
`SLP`

. If we learn what these individual concepts mean, we get an
insight into the combination.`Permutation`

### What is an permutation?

A permutation is a bijection from one set to the other. Basically it sends every
element of a set for example

to an element of that set. For example`0``,` `1``,` `2`

`0 -> 1
1 -> 2
2 -> 0
`

### What is an SLP?

is short for `SLP`*straight line program*. It is an description of a
calculation which can be performed with other group elements. The implementation
used in this project deviate a little from more traditional programs. It is more
akin a *Abstract Syntax Tree*.

For example, the following representation of a

,`SLP`

`(Product
(Generator 0)
(Inverse (Generator 1)))
`

together with a morphism that sends

to `Generator 0`

`(``1` `2``)`

and `Generator ``1`

to `(``1` `2` `3``)`

corresponds with the permutation `(``2` `3``)`