3

我想实现一个非常简单的自动机，它限制一和零列表中连续 1 的数量（例如 [0,1,1,0,1,1,1]）。

我的自动机看起来像这样：

% 'Day' is a list of clpfd variables
% 'Allowed' is an integer
%
% consecutiveOnes(+Day, +Allowed)
consecutiveOnes(Day, Allowed) :-

    automaton(Day, _, Day,
        [source(n)],
        [
         arc(n, 0, n, [0]  ),
         arc(n, 1, n, [C+1])
        ],
        [C],
        [0],
        [_N]
    ).



% example 1:
%   consecutiveOnes([0,0,0,1,1,1], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.

% example 2:
%   consecutiveOnes([0,1,1,1,0,0], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.


% example 3:
%   consecutiveOnes([0,1,1,0,0,0], 2)  -> there are only two consecutive 1s and we allow 2 -> OK

如何将C指定计数器的约束添加C <= Allowed到上面的 Prolog 代码中？

4

2 回答 2

3

最好用其他状态来表述这一点。例如，最多两个连续的 1：

:- use_module(library(clpfd)).

at_most_two_consecutive_ones(Day) :-
    automaton(Day,
        [source(n),sink(n),sink(n1),sink(n2)],
        [arc(n, 0, n),
         arc(n, 1, n1),
         arc(n1, 1, n2),
         arc(n1, 0, n),
         arc(n2, 1, false),
         arc(n2, 0, n)
        ]).

示例查询：

?- at_most_two_consecutive_ones([0,0,0,1,1,1]).
false.

?- at_most_two_consecutive_ones([0,1,1,0,1,1]).
true.

?- at_most_two_consecutive_ones([0,1,1,0,1,0]).
true.

对于更通用的解决方案，您必须在给定最大运行长度时按需构建自动机。

于 2013-07-21T15:02:21.183 回答
1

我相信以下代码是您正在寻找的：

:- use_module(library(clpfd)).

consecutiveOnes(Day, Allowed) :-
    automaton(Day, _, Day,
        [source(n),sink(n)],
        [
         arc(n, 0, n, [0]  ),
         arc(n, 1, n, (C #< Allowed -> [C+1]))
        ],
        [C],[0],[_N]
    ).

请注意对原始代码的两个更改：（1）我在源和接收器列表中添加了一个接收器（n）。否则它将拒绝每个序列。(2) 我添加了 C < 允许的条件。如果条件不满足，则没有别的，所以它失败。

一些示例查询：

| ?- consecutiveOnes([0,1,1,0],1).                                              
no                                 
| ?- consecutiveOnes([0,1,1,0],2).
yes
| ?- consecutiveOnes([0,1,1,0,1,1,1],2).
no
| ?- consecutiveOnes([0,1,1,0,1,1,0],2).
yes
于 2018-06-19T10:15:48.437 回答