list - Prolog:参数未充分实例化

Question

我有以下问题:

Generate all sub-strings of a length 2*n+1, formed from values of 0, 1 or -1, so a1 = ..., a2n+1 = 0 and |a(i+1) - ai| = 1 or 2, for every 1 <= i <= 2n.

这是我做的:

change(0).
change(1).
change(-1).

%gets the last element from a list
lastE([X],X).
lastE([_|L],X) :-
    last(L,X).

%checks if |N-M|=1 or 2
calc(N,M) :-
    (  1 is abs(N-M)
    ;  2 is abs(N-M),
       !
    ).

%generates all lists of length N with values -1,0,1
generate([],0) :-
   !.
generate([H|T],N):-
    change(H),
    N1 is N-1,
    generate(T,N1).

%validates a list to be correct (last element=0, |a(i+1) - ai| = 1 or 2)
valid(L) :-
   valid(L,_,3).

valid([E],_,_) :-
    lastE([E],0).
valid([H|[H1|T]],_,3) :-
    valid([H1|T],H,H1).
valid([_|[H1|T]],N,M) :-
    calc(N,M),
    valid([H1|T],M,H1).

以上所有代码都可以正常工作(我测试过)。但是对于 genAll 的以下代码，我得到了 Arguments are not enoughly instantiated 错误。

genAll(N) :-
    N1 = 2*N,
    N2 = N1+1,
    generate(L1,N2),
    valid(L1),
    write('['),
    printl(L1).

printl([]) :-
    write(']').
printl([0|T]) :-
    write('0 '),
    printl(T).
printl([1|T]) :-
    write('1 '),
    printl(T).
printl([-1|T]) :-
    write('-1 '),
    printl(T).

我不确定哪里出了问题。

Answer 1

在这个答案(主要是猜测)中，我们使用 clpfd .

:- use_module(library(clpfd)).n_qfd33721532(N, Zs) :-   Zs = [E|Es],   N*2 + 1 #= L,   length(Zs, L),   Zs ins -1..1,   last(Zs, 0),   chain_neq(Es, E).chain_neq([], _).chain_neq([E1|Es], E0) :-   E0 #\= E1,   chain_neq(Es, E1).

示例查询:

?- n_qfd33721532(N, Zs), labeling([], Zs).  N = 0, Zs = [0]; N = 1, Zs = [-1, 1, 0]; N = 1, Zs = [ 0,-1, 0]; N = 1, Zs = [ 0, 1, 0]; N = 1, Zs = [ 1,-1, 0]; N = 2, Zs = [-1, 0,-1, 1, 0]; N = 2, Zs = [-1, 0, 1,-1, 0]; N = 2, Zs = [-1, 1,-1, 1, 0]; N = 2, Zs = [-1, 1, 0,-1, 0]; N = 2, Zs = [-1, 1, 0, 1, 0]; N = 2, Zs = [ 0,-1, 0,-1, 0]; N = 2, Zs = [ 0,-1, 0, 1, 0]; N = 2, Zs = [ 0,-1, 1,-1, 0]; N = 2, Zs = [ 0, 1,-1, 1, 0]; N = 2, Zs = [ 0, 1, 0,-1, 0]; N = 2, Zs = [ 0, 1, 0, 1, 0]; N = 2, Zs = [ 1,-1, 0,-1, 0]; N = 2, Zs = [ 1,-1, 0, 1, 0]; N = 2, Zs = [ 1,-1, 1,-1, 0]; N = 2, Zs = [ 1, 0,-1, 1, 0]; N = 2, Zs = [ 1, 0, 1,-1, 0]; N = 3, Zs = [-1, 0,-1, 0,-1, 1, 0] ...