Clingo ASP - Permutation of a list and absolute differences of its elements

Question

I am trying to learn and understand Answer Set Programming with Clingo (https://potassco.org/clingo/run/). Here is a task I am struggling with now:

Find the sequence s = (s1, s2, ..., sn) with the following properties:

s is a permutation of the set {0, 1, ..., n-1};
the sequence v = (|s2-s1|, |s3-s2|, ..., |sn-sn-1|) is a permutation of the set {1, 2, ..., n-1};

Solve this problem for n = 11.

I have managed to create an algorithm for this in C#, but I have a hard time translating this into ASP.

Here is the code in C#:

namespace X;

using System;
using System.Linq;

// Find the sequence s = (s1, s2, ..., sn) with the following properties:
// - s is a permutation of the set {0, 1, ..., n-1};
// - the sequence v = (|s2-s1|, |s3-s2|, ..., |sn-sn-1|) is a permutation of the set {1, 2, ..., n-1};
// Solve this problem for n = 11.
class Program
{
    public static void Main()
    {
        const int n = 11;
        
        // Set {0, 1, .., n-1}.
        int[] set = new int[n];

        for (int i = 0; i < n; i++)
        {
            set[i] = i;
        }

        // Set {1, 2, .., n-1}.
        int[] set2 = new int[n - 1];

        for (int i = 0; i < n - 1; i++)
        {
            set2[i] = i + 1;
        }

        bool found = false;
        
        int[] v = new int[n - 1];

        // Generating all permutations, one by one.
        ForAllPermutation(set, (permutation) =>
        {
            // Creating the sequence v.
            for (int i = 0; i < n - 1; i++)
            {
                v[i] = Math.Abs(permutation[i + 1] - permutation[i]);
            }

            Array.Sort(v);

            // Is v a permutation of {1, 2, ..., n-1}?
            if (v.SequenceEqual(set2))
            {
                Console.WriteLine("Found s=({0})", string.Join(", ", permutation));
                found = true;
                
                // Even if the sequence is found, we continue to find other solutions.
                return false;
            }

            return false;
        });

        if (!found)
        {
            Console.WriteLine("Not found.");
        }
    }

    // Source of the permutation generating algorithm:
    // https://stackoverflow.com/a/36634935/17360812
    public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
    {
        int countOfItem = items.Length;

        if (countOfItem <= 1)
        {
            return funcExecuteAndTellIfShouldStop(items);
        }

        var indexes = new int[countOfItem];

        if (funcExecuteAndTellIfShouldStop(items))
        {
            return true;
        }

        for (int i = 1; i < countOfItem;)
        {
            if (indexes[i] < i)
            { 
                if ((i & 1) == 1)
                {
                    Swap(ref items[i], ref items[indexes[i]]);
                }
                else
                {
                    Swap(ref items[i], ref items[0]);
                }

                if (funcExecuteAndTellIfShouldStop(items))
                {
                    return true;
                }

                indexes[i]++;
                i = 1;
            }
            else
            {
                indexes[i++] = 0;
            }
        }

        return false;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        (a, b) = (b, a);
    }
}

What it does is it generates permutations of the set {0, 1, ..., n-1} sequentially, one by one, and constructs the set v = {|s2-s1|, |s3-s2|, ..., |sn-sn-1|} for each permutation. If that set is a permutation of the set {1, 2, ..., n-1}, then we have a solution.

The program returns multiple solutions, for example s=(5,4,6,3,7,2,8,1,9,0,10) and s=(5,6,4,7,3,8,2,9,1,10,0).

However, I am having a hard time re-creating this in ASP. First of all, I am unable to create a rule for permutations at all. I have tried this solution from here, but I get errors:

clingo version 5.7.0
Reading from stdin
-:1:10-11: error: syntax error, unexpected [

-:2:10-11: error: syntax error, unexpected [

-:4:6-7: error: syntax error, unexpected [, expecting ) or ;

-:5:6-7: error: syntax error, unexpected [, expecting ) or ;

*** ERROR: (clingo): parsing failed

I have also tried slightly modifying the solution from (here)[]:

% Define the integers from 0 to 10
1 { num(X,Y) : Y=0..10 } 1 :- X=0..10.

% Define the sequence s as a permutation of the numbers from 0 to 10
1 { s(X,Y) : Y=0..10 } 1 :- X=1..11.
:- not 1 { s(X,Y) : Y=0..10 } 1, X=1..11.
:- s(X,Y), s(X,Z), Y!=Z, X=1..11.

% Define the sequence v as a permutation of the numbers from 1 to 10
1 { v(X,Y) : Y=1..10 } 1 :- X=1..10.
:- not 1 { v(X,Y) : Y=1..10 } 1, X=1..10.
:- v(X,Y), v(X,Z), Y!=Z, X=1..10.

% Define the absolute differences between adjacent elements of s
d(X,Y,Z) :- s(X+1,Y), s(X,Z), X=1..10.

% Ensure that the absolute differences form a permutation of the numbers from 1 to 10
:- d(X,Y,Z), not v(X,Y), Y=1..10, X=1..10.
:- v(X,Y), not d(X,Y,Z), Y=1..10, X=1..10.

But again, it fails:

clingo version 5.7.0
Reading from stdin
-:19:1-43: error: unsafe variables in:
  #void:-#range(Y,1,10);#range(X,1,10);[#inc_base];0=0;#range(#Range1,1,10);#range(#Range0,1,10);v(X,Y);(#Range0+0)=Y;(#Range1+0)=X;X=(#Range1+0);Y=(#Range0+0);not d(X,Y,Z).
-:19:22-23: note: 'Z' is unsafe

*** ERROR: (clingo): grounding stopped because of errors

How can I approach this problem at all, and what can I do to fix these errors?

A variable is unsafe when it does not appear in positive literals in the body, but only in negated ones, as X that is present only in the negated literal not d(X,Y,Z) — damianodamiano, Apr 07 '23 at 06:50
You should add a positive literal that contains Z. Howver, it is not immediatly clear to me what this should be — damianodamiano, Apr 07 '23 at 14:17

Clingo ASP - Permutation of a list and absolute differences of its elements

0 Answers0

Linked