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

この以前の回答では、SICStus Prolog predicateを利用しました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

この回答では、2 つの異なる "フレーバー" を使用しています: とです。

:- use_module (ライブラリ(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),
    length (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 に答える