基于Clingo的排列与绝对差序列问题求解及ASP代码修正

问题需求 #

寻找序列s=(s₁,s₂,…,s₁₁)满足：

• s是集合{0,1,…,10}的排列；
• 相邻元素差的绝对值序列v=(|s₂-s₁|,|s₃-s₂|,…,|s₁₁-s₁₀|)是集合{1,2,…,10}的排列。

C#实现参考 #

已通过C#枚举所有排列验证解的存在性，示例解如s=(5,4,6,3,7,2,8,1,9,0,10)，代码如下：

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);
    }
}

ASP代码问题分析 #

1. 语法错误（参考Prolog代码导致） #

ASP与Prolog语法差异较大，Prolog的列表语法[X|Y]在ASP中不适用，直接照搬会触发解析错误。ASP需用事实、规则和选择规则建模，不能直接使用Prolog的列表结构。

2. 变量不安全错误 #

原ASP代码中，规则:- v(X,Y), not d(X,Y,Z), Y=1..10, X=1..10.里的变量Z未在任何正文字（非否定原子）中出现，属于不安全变量——Clingo要求规则中所有变量必须出现在至少一个正文字中，否则无法完成实例化。

同时原代码对d(X,Y,Z)的定义逻辑错误：d应表示位置X处的差为D，而非存储前后元素值，这导致后续关联v时逻辑混乱。

修正后的ASP代码 #

% 定义基础常量：n=11，元素范围0-10，差范围1-10
#const n=11.
element(0..n-1).
diff(1..n-1).
position(1..n).
diff_pos(1..n-1).

% 约束序列s：每个位置唯一对应一个元素，每个元素唯一出现在一个位置
1 { s(P, E) : element(E) } 1 :- position(P).
1 { s(P, E) : position(P) } 1 :- element(E).

% 计算相邻位置的绝对差，存入diff_at(P, D)（P为差的位置，1-10）
diff_at(P, D) :- 
    position(P), position(P+1),
    s(P, E1), s(P+1, E2),
    D = abs(E1 - E2),
    diff(D).

% 约束差序列是1-10的排列：每个差位置对应唯一差，每个差对应唯一位置
1 { diff_at(P, D) : diff(D) } 1 :- diff_pos(P).
1 { diff_at(P, D) : diff_pos(P) } 1 :- diff(D).

% 按位置顺序输出序列s的元素
#show s(P, E) : position(P).

代码解释 #

1. 基础定义：用#const统一管理n的值，声明元素、差、位置的范围，避免硬编码。
2. 序列s的约束：通过两个选择规则确保s(P,E)是排列——每个位置P恰好选一个元素E，每个元素E恰好出现在一个位置P。
3. 差的计算：通过规则diff_at(P,D)自动计算相邻元素的绝对差，并用diff(D)过滤掉非1-10的无效值。
4. 差序列的排列约束：同样用选择规则确保diff_at(P,D)是1-10的排列，保证所有差都被使用且不重复。
5. 输出控制：用#show指定按位置顺序输出s的元素，便于直接查看完整序列。

运行说明 #

将代码保存为sequence.lp，执行命令：

clingo sequence.lp 0

参数0表示输出所有解，默认仅输出一个解。运行后会得到类似如下的输出（示例）：

Answer: 1
s(1,5) s(2,4) s(3,6) s(4,3) s(5,7) s(6,2) s(7,8) s(8,1) s(9,9) s(10,0) s(11,10)

内容的提问来源于stack exchange，提问作者nooblet2