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