Simple Permutations

Original Simple Permutations by Ruth Hoffmann and Gökberk Koçak, edited by András Salamon. Adapted by Alex Gallagher.

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 σ is a factor of contiguous values of σ such that their indices are consecutive. For example, in the permutation π=346978215, π(4)π(5)π(6)=978 is an interval, whereas π(1)π(2)π(3)π(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 π=346978215 is not simple as we have seen in the example above that it contains an interval, on the other hand σ=526184937 is simple as there are no intervals of length strictly greater than 1, except the whole of σ. See Hof15 for more information on permutation patterns and simple permutations.

Parameter

!source <(curl -s https://raw.githubusercontent.com/conjure-cp/conjure-notebook/v0.0.2/scripts/install-colab.sh)
%load_ext conjure

Installing Conjure...
Conjure: The Automated Constraint Modelling Tool
Release version 2.4.0
Repository version a7382e3d9 (2022-11-21 10:41:03 +0000)

Conjure extension is loaded.
For usage help run: %conjure_help

%%conjure
letting n be 5

{}

Enumeration/Generation Model

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.

%%conjure
find perm : sequence (bijective, size n) of int(1..n)

{'perm': [1, 2, 3, 4, 5]}

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.

%%conjure
letting example be [ num | num : int(1..5), num != 3 ]

{'perm': [1, 2, 3, 4, 5]}

This is an example which creates a 1-dimensional matrix of nums where none of the entries are 3. We allow also for letting statements inside the matrix comprehensions, which allow us to define intermediary statements.

%%conjure
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)]]
    )

{'perm': [2, 4, 1, 5, 3]}

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.

Solving

Using n = 5, the sample solution is 'perm': [2, 4, 1, 5, 3].

To find all solutions, type:

%%conjure --number-of-solutions=all
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)]]
    )

[{'perm': [2, 4, 1, 5, 3]},
 {'perm': [2, 5, 3, 1, 4]},
 {'perm': [3, 1, 5, 2, 4]},
 {'perm': [3, 5, 1, 4, 2]},
 {'perm': [4, 1, 3, 5, 2]},
 {'perm': [4, 2, 5, 1, 3]}]

For n be 5 you should get 6 solutions.

Checking Model with Instances

What the model will tell us is that the permutation is simple (true) or not.

%conjure_clear

Conjure model cleared

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

{}

%%conjure
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)]]
    )

{'result': False}

This is a non-simple permutation.

%conjure_clear

Conjure model cleared

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

{}

%%conjure
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)]]
    )

{'result': True}

It is important to clear the model between instances when redefining variables. If we attempt to run the test again without using %conjure_clear, the solutions will not reflect the instance provided in the cell.

%%conjure
letting n be 5
letting perm be sequence( 1, 4, 2, 5, 3)
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)]]
    )

'No solution'