循环升序列表的序言约束

Question

我想在 SWI-Prolog 中使用 CLP（特别是 FD）制定一个约束，即列表是循环升序列表。

我的意思是一个常规的 Prolog 列表，它被用来表示一个循环列表，这样列表及其所有旋转表示相同的循环列表。约束是这些轮换之一是严格升序列表。

例如，对于8个变量，我可以这样表示：

cyclical_ascending([A,B,C,D,E,F,G,H]) :-
    B #> A,
    C #> B,
    D #> C,
    E #> D,
    F #> E,
    G #> F,
    H #> G,
    A #> H.

除了其中一个约束必然不成立，而所有其他约束都成立。而且我不know/care，哪一个

如何做到这一点？

Answer 1

我想到了几种定义 cyclical_ascending 规则的方法：

如果列表的旋转之一是 cyclical_ascending，则列表是升序
一个列表是 cyclical_ascending 如果 (a) 没有相邻的对 X, Y 其中 X >= Y，或者 (b) 只有一个这样的对并且 Head > Tail.

我认为第二个定义会导致更有效的解决方案，所以我会尝试一下。我们将跟踪列表的头部，并计算是否有单个

:- use_module(library(clpfd)).

cyclical_ascending([]).     % Empty list is a degenerate cyclical ascending list
cyclical_ascending([H|T]) :-
    cyclical_ascending([H|T], H, 0).

cyclical_ascending([_], _, 0).      % List is ascending
cyclical_ascending([X], H, 1) :-    % A cycle of list is ascending
    X #< H.
cyclical_ascending([X,Y|T], H, C) :-
    X #< Y,
    cyclical_ascending([Y|T], H, C).
cyclical_ascending([X,Y|T], H, C) :-
    X #>= Y,
    C #< 1,
    C1 #= C + 1,
    cyclical_ascending([Y|T], H, C1).

或者另一种写法是避免计数器而是使用另一个辅助谓词：

cyclical_ascending([]).     % Empty list is a degenerate cyclical ascending list
cyclical_ascending([H|T]) :-
    cyclical_ascending([H|T], H).

cyclical_ascending([_], _).
cyclical_ascending([X,Y|T], H) :-
    X #< Y,
    cyclical_ascending([Y|T], H).
cyclical_ascending([X,Y|T], H) :-
    X #>= Y,
    cyclical_ascending1([Y|T], H).

cyclical_ascending1([X], H) :-
    X #< H.
cyclical_ascending1([X,Y|T], H) :-
    X #< Y,
    cyclical_ascending1([Y|T], H).

正在尝试一个简单的查询：

2 ?- length(L, 4), L ins 1..4, cyclical_ascending(L).
L = [1, 2, 3, 4] ;
L = [2, 3, 4, 1] ;
L = [3, 4, 1, 2] ;
L = [4, 1, 2, 3] ;
false.

3 ?-

Answer 2

这是 ECLiPSe 的解决方案，但您可以对 SWI/clpfd 使用相同的想法。对于每一对 X,Y 的相邻列表元素，我们计算一个布尔值 B 如果该对是升序的则为 0，否则为 1。要满足您的 "cyclical ascending" 条件，Bs 中只有一个必须是 1.

:- lib(ic).

cycasc(Xs) :-
    Xs = [X1|_], append(Xs, [X1], Xs1),                      % for convenience, append the first element to the end of the list
    ( fromto(Xs1,[X,Y|Xs2],[Y|Xs2],[_]), foreach(B,Bs) do    % make a list of booleans that indicate non-ascending pairs
        B #= (X#>=Y)
    ),
    sum(Bs) #= 1.                                            % there must be exactly one

样本运行：

?- length(Xs, 4), Xs #:: 1..4, cycasc(Xs), labeling(Xs).
Xs = [1, 2, 3, 4]
Yes (0.00s cpu, solution 1, maybe more)
Xs = [2, 3, 4, 1]
Yes (0.00s cpu, solution 2, maybe more)
Xs = [3, 4, 1, 2]
Yes (0.00s cpu, solution 3, maybe more)
Xs = [4, 1, 2, 3]
Yes (0.00s cpu, solution 4)

循环升序列表的序言约束

Prolog constraint for cyclical ascending list

list

prolog

clpfd