Ограничьте два списка, чтобы начать с N последовательных элементов в общей сложности с помощью CLP (FD)

Question

Я пытаюсь ограничить два списка, начиная с N последовательных элементов (E), используя CLP (FD). Вот пример: пусть L1 и L2 два списка размера 6, элементы принадлежат к области [0, 1], E = 1, и N = 3, то предикат constraint(+L1, +L2, +N) обеспечат следующие возможные решения:

L1 = [1, 1, 1, 0, _, _], L2 = [0, _, _, _, _, _]; 
L1 = [1, 1, 0, _, _, _], L2 = [1, 0, _, _, _, _]; 
L1 = [1, 0, _, _, _, _], L2 = [1, 1, 0, _, _, _]; 
L1 = [0, _, _, _, _, _], L2 = [1, 1, 1, 0, _, _]. 

Для списков размера 3, следующее было бы приемлемо:

L1 = [1, 1, 1], L2 = [0, _, _]; 
L1 = [1, 1, 0], L2 = [1, 0, _]; 
L1 = [1, 0, _], L2 = [1, 1, 0]; 
L1 = [0, _, _], L2 = [1, 1, 1]. 

в конце концов я хочу обобщить это на произвольное число списков и области, но это самый маленький эквивалент проблема, которую я мог думать.

---

Вот мой (неудачная) попытка до сих пор:

:- use_module(library(clpfd)). 

constseq([], _, 0). 
constseq([L|_], A, 0) :- L #\= A. 
constseq([A|Ls], A, N) :- N1 #= N - 1, constseq(Ls, A, N1). 

constraint(L1, L2, N) :- 
    SL1 + SL2 #= N, 
    constseq(L1, 1, SL1), 
    constseq(L2, 1, SL2). 

main(L1, L2) :- 
    length(L1, 6), 
    length(L2, 6), 
    constraint(L1, L2, 3). 

Хотя это работает, обратите внимание, что я генерации решений через возвратов, а не пользуясь CLP (FD) в сделайте грязную работу. Я пытаюсь понять, как это сделать, и я уже смотрю на предикаты, такие как chain/2, и монстры вроде automaton/3, но во мне что-то говорит, что должно быть более простое решение для этого ...

Answer 1

Вдохновленный на SICStus example из exactly/3, вот моя последняя попытка:

constseq_(_, [], _, 0). 
constseq_(X, [Y|L], F, N) :- 
    X #= Y #/\ F #<=> B, 
    N #= M+B, 
    constseq_(X, L, B, M). 

constseq(L, E, N) :- 
    constseq_(E, L, 1, N). 

Answer 2

Я бы написать это следующим образом (с использованием ECLiPSe с library(ic)):

:- lib(ic). 
:- lib(ic_global). 

constraint(Xs, Ys, N) :- 
    Xs #:: 0..1, 
    Ys #:: 0..1, 
    sum(Xs) + sum(Ys) #= N, 
    ordered(>=, Xs), 
    ordered(>=, Ys). 

который ГИ ves требуемые решения:

?- length(Xs,6), length(Ys,6), constraint(Xs,Ys,3), labeling(Xs), labeling(Ys). 
Xs = [0, 0, 0, 0, 0, 0] 
Ys = [1, 1, 1, 0, 0, 0] 
Yes (0.00s cpu, solution 1, maybe more) ? ; 
Xs = [1, 0, 0, 0, 0, 0] 
Ys = [1, 1, 0, 0, 0, 0] 
Yes (0.00s cpu, solution 2, maybe more) ? ; 
Xs = [1, 1, 0, 0, 0, 0] 
Ys = [1, 0, 0, 0, 0, 0] 
Yes (0.00s cpu, solution 3, maybe more) ? ; 
Xs = [1, 1, 1, 0, 0, 0] 
Ys = [0, 0, 0, 0, 0, 0] 
Yes (0.00s cpu, solution 4)