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.9/scripts/install-colab.sh)
%load_ext conjure

Installing Conjure version v2.5.1 and Conjure Notebook version v0.0.9...
Conjure is already installed.
Conjure notebook is already installed.
Conjure: The Automated Constraint Modelling Tool
Release version 2.5.1
Repository version a9cbc2e (2023-11-07 23:44:00 +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+ --solver=minion
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+ --solver=minion
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+ --solver=minion
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+ --solver=minion --number-of-solutions=all

{"conjure_solutions": [{"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
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
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}

You need to ensure that the magic %conjure+ is used on cells that append to the code written in previous cells. For example the next cell creates a new conjure model, so runs correctly. But the cell below that writes the model on top of the existing model, so produces an error as you try to reassign the value of n.

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

{"result": false}

%%conjure+
letting n be 10

Exception: Error:
    Redefinition of name: n
    When trying to define it as an alias for 10
    It was already defined as an alias for 5