4

如何限制列表中数字的重复？

以下代码示例中合适的约束是什么？

limit(X) :-
    length(X,10),
    domain(X,1,4),
    % WANTED CONSTRAINT: maximum repetition of each number is 5 times.
    labeling([],X).

一些示例查询和预期答案：

?- limit([1,1,1,1,1,1,1,1,1]).
false.

?- limit([1,1,1,1,1,2,2,2,2,2]).
true.
4

4 回答 4

2

这有效，L 是从 1 到 4 的每个数字的重复次数列表。

:- use_module(library(clpfd)).

limit(X) :-
    length(L, 4),
    L ins 0..5,
    sum(L, #=, 10),
    label(L),    
    maplist(make_list, [1,2,3,4], L, LX),
    flatten([LX],X).


make_list(Val, Nb, L) :-
    length(L, Nb),
    L ins Val .. Val.

问题是这些数字是按值分组的。代码可以概括为

limit(X, Min, Max, Len, Rep) :-
    Nb is Max -Min + 1,
    length(L, Nb),
    L ins 0..Rep,
    sum(L, #=, Len),
    label(L),
    numlist(Min, Max, Lst),
    maplist(make_list, Lst, L, LX),
    flatten([LX],X).

你试试： limit(X, 1, 4, 10, 5)。

于 2013-03-30T23:17:46.937 回答
2

在上一个答案中，我们使用了 SICStus Prolog 谓词global_cardinality/2。作为非约束替代方案，我们也可以selectd/3这样使用：

multi_selectd_rest([],Ds,Ds)。
multi_selectd_rest([Z|Zs],Ds0,Ds) :-
   选择（Z，Ds0，Ds1），
   multi_selectd_rest（Zs，Ds1，Ds）。

充分利用它，limited_repetitions__selectd/3我们定义：

limited_repetitions__selectd(Zs) :-
   长度（Zs，10），
   multi_selectd_rest(Zs,[ 1 ,1,1,1,1, 2 ,2,2,2,2, 3 ,3,3,3,3, 4 ,4,4,4,4],_)。

再次，让我们测量计算解决方案数量所需的时间！

?- call_time ( call_succeeds_n_times (limited_repetitions__selectd (_),N), T_ms)。
N = 965832，T_ms = 4600。
于 2015-11-09T13:12:24.377 回答
2

在这个答案中，我们使用了两种不同 “风味”：和。

:- use_module ( library(clpfd) )。

limited_repetitions__SICStus(Zs) :-
   长度(Zs, 10),
   域(Zs, 1, 4),
   域([C1,C2,C3,C4], 0, 5),
   global_cardinality (Zs, [1-C1,2-C2,3-C3,4-C4])，
   标签([], Zs)。

limited_repetitions__gprolog(Zs) :-
   长度(Zs, 10),
    fd_domain (Zs, 1, 4),
    maplist ( fd_atmost (5,Zs), [1,2,3,4]),
    fd_labeling (Zs)。

使用SICStus Prolog版本 4.3.2 和GNU Prolog 1.4.4运行的简单示例查询：

?- limited_repetitions__SICStus(Zs)。% ?- limited_repetitions__gprolog(Zs)。
  Zs = [1,1,1,1,1,2,2,2,2,2] % Zs = [1,1,1,1,1,2,2,2,2,2]
; Zs = [1,1,1,1,1,2,2,2,2,3] % ; Zs = [1,1,1,1,1,2,2,2,2,3]
; Zs = [1,1,1,1,1,2,2,2,2,4] % ; Zs = [1,1,1,1,1,2,2,2,2,4]
; Zs = [1,1,1,1,1,2,2,2,3,2] % ; Zs = [1,1,1,1,1,2,2,2,3,2]
; Zs = [1,1,1,1,1,2,2,2,3,3] % ; Zs = [1,1,1,1,1,2,2,2,3,3]
; Zs = [1,1,1,1,1,2,2,2,3,4] % ; Zs = [1,1,1,1,1,2,2,2,3,4]
; Zs = [1,1,1,1,1,2,2,2,4,2] % ; Zs = [1,1,1,1,1,2,2,2,4,2]
... % ...

让我们测量计算解决方案数量所需的时间！

call_succeeds_n_times(G_0, N) :-
    findall (t, call(G_0), Ts),
   长度(Ts, N)。

?- call_time (call_succeeds_n_times(limited_repetitions__SICStus(_), N), T_ms)。
N = 965832，T_ms = 6550。% w/SICStus Prolog 4.3.2

?- call_time(call_succeeds_n_times(limited_repetitions__gprolog(_), N), T_ms)。
N = 965832，T_ms = 276。% w/GNU Prolog 1.4.4
于 2015-11-07T07:22:22.163 回答
1

这是一种方法，但不适用于序列：

:- [library(clpfd)].

limit_repetition(Xs, Max) :-
    maplist(vs_n_num(Xs, Max), Xs).

vs_n_num(Vs, Max, X) :-
    maplist(eq_b(X), Vs, Bs),
%   sum(Bs, #=, EqC),
%   EqC #=< Max.
    sum(Bs, #=<, Max).

eq_b(X, Y, B) :- X #= Y #<==> B.

vs_n_num/3 是您可以在docs中找到的内容的改编版本。

这是一种分隔序列的方法：

limit_repetition([X|Xs], Max) :-
    limit_repetition(X, 1, Xs, Max).

limit_repetition(X, C, [Y|Xs], Max) :-
    X #= Y #<==> B,
    ( B #/\ C + B #=< Max #/\ D #= C + B ) #\/ ( (#\ B) #/\ D #= 1 ),
    limit_repetition(Y, D, Xs, Max).
limit_repetition(_X, _C, [], _Max).

产量

?- length(X,4), X ins 1..4, limit_repetition(X, 1) ,label(X).
X = [1, 2, 1, 2] ;
X = [1, 2, 1, 3] ;
...

似乎以前的版本与您的示例更相关。

于 2013-03-30T19:43:04.813 回答