# Simple Permutations

Authors: Ruth Hoffmann and Gökberk Koçak, edited by András Salamon

## Problem

Let a permutation be a sequence of length \(n\) consisting of numbers between 1 and \(n\), in any order with each number occurring exactly once.

An interval in a permutation \({\sigma}\) is a factor of contiguous values of σ such that their indices are consecutive.
For example, in the permutation \({\pi} = 346978215\), \({\pi}(4){\pi}(5){\pi}(6) = 978\) is an interval, whereas \({\pi}(1){\pi}(2){\pi}(3){\pi}(4) = 3469\) is not.
It is easy to see that every permutation of length \(n\) has intervals of length 0, 1 and \(n\) , at least. The permutations of length \(n\) that **only** contain intervals of length 0, 1 and \(n\) are said to be simple.
So for example the permutation \({\pi} = 346978215\) is not simple as we have seen in the example above that it contains an interval, on the other hand \({\sigma} = 526184937\) is simple as there are no intervals of length strictly greater than 1, except the whole of \({\sigma}\).
See [Hof15] for more information on permutation patterns and simple permutations.

## Enumeration/Generation Model

```
language Essence 1.3
given n : int
find perm : sequence (bijective, size n) of int(1..n)
such that
and([ max(subs) - min(subs) + 1 != |subs| |
i : int(1..n-1), j : int(2..n),
i < j,
!(i = 1 /\ j = n),
letting subs be [perm(k) | k : int(i..j)]]
)
```

```
given n : int
find perm : sequence (bijective, size n) of int(1..n)
```

We define the size of the permutation to be `n`

and we are trying to find all the permutations `perm`

to contain the integers 1 to `n`

, by specifying that it is `bijective`

.

```
```

The idea of our approach is the property of an interval, where when sorted it creates a complete range. This can be translated to checking that the difference between the maximal and the minimal elements of the interval is not equal to the cardinality of the interval.

We have one constraint to say that there are only intervals of length 0,1 and `n`

.
This constraint is defined as a matrix comprehension, which will build a matrix consisting of only boolean entries.
We then check the matrix with an `and`

constraint, to spot if there are any `false`

entries, which would mean that we have an interval.

```
[ num | num : int(1..5), num != 3 ]
```

This is an example which creates a 1-dimensional matrix of `num`

s where none of the entries are `3`

.
We allow also for `letting`

statements inside the matrix comprehensions, which allow us to define intermediary statements.

```
and([ max(subs) - min(subs) + 1 != |subs| |
i : int(1..n-1), j : int(2..n),
i < j,
!(i = 1 /\ j = n),
letting subs be [perm(k) | k : int(i..j)]]
)
```

We extract `i`

and `j`

to be the beginning and the end of the interval, and we need to make sure that `i`

is less than `j`

to have the right order.
As we do not want to include the whole permutation as an interval, we restrict that `i`

and `j`

cannot be simultaneously at the respective ends of the permutation.
The final line of the comprehension sets up the continuous subsequences.
On the left hand side of the matrix comprehension we use the interval property that when it is turned into a sorted set it is a complete range.

## Parameter

```
language Essence 1.3
letting n be 5
```

## Solving

Using the ESSENCE pipeline, we can solve our sample size by typing the following:

```
conjure solve simple_perm-gen-model.essence simple_perm-gen-param.essence-param
```

You will be then returned one `.solution`

file, which contains a sample solution such as:

```
language Essence 1.3
letting perm be sequence(2, 4, 1, 5, 3)
```

If you look for an enumeration (or generation) of all solutions, type:

```
conjure solve simple_perm-gen-model.essence simple_perm-gen-param.essence-param --number-of-solutions=all
```

The results will be saved into many (for `n be 5`

you should get 6) `.solution`

files which will contain a solution each.

## Checking Model

```
language Essence 1.3
given n : int
given perm : sequence (bijective, size n) of int
find result : bool
such that
result = and([ max(subs) - min(subs) + 1 != |subs| |
i : int(1..n-1), j : int(2..n),
i < j,
!(i = 1 /\ j = n),
letting subs be [perm(k) | k : int(i..j)]]
)
```

```
given n : int
given perm : sequence (size n) of int
```

We define the size of the permutation to be `n`

and the permutation `perm`

to contain integers.

```
find result : bool
```

What the model will tell us is that the permutation is simple (`true`

) or not.

## Instances

```
letting n be 5
letting perm be sequence( 1, 4, 2, 5, 3)
```

This a non-simple permutation.

```
letting n be 5
letting perm be sequence(2, 4, 1, 5, 3)
```

This is a simple permutation.

## Solving

Using the ESSENCE pipeline, we can solve our sample instance by typing the following:

```
conjure solve simple_perm-check-model.essence simple_perm-check-instance.essence-param
```

The result will be saved into a `.solution`

file which will look something like this (or say `false`

):

```
language Essence 1.3
letting result be true
```