CODEWITHSUNDEEP
prologconstraint-programmingclpfd
mmgro27
mmgro27

Reputation: 515

CLP in Prolog involving consecutive sums in a list

Example of my CLP problem (this is a small part of a larger problem which uses the clpfd library):

For a list of length 5, a fact el_sum(Pos,N,Sum) specifies that the N consecutive elements starting from position Pos (index from 1) have sum equal to Sum. So if we have

el_sum(1,3,4).
el_sum(2,2,3).
el_sum(4,2,5).

Then [1,2,1,4,1] would work for this example since 1+2+1=4, 2+1=3, 4+1=5.

I'm struggling with how to even start using the el_sum's to find solutions with an input list [X1,X2,X3,X4,X5]. I'm thinking I should use findall but I'm not really getting anywhere.

(My actual problem is much bigger than this so I'm looking for a solution that doesn't just work for three facts and a small list).

Thanks!

Upvotes: 1

Views: 168

Answers (2)

CapelliC
CapelliC

Reputation: 60014

Not sure this will help, I don't understand your workflow... from where the list do come ? Anyway

:- [library(clpfd)].

el_sum(Pos,N,Sum) :-
    length(L, 5),
    L ins 0..100,
    el_sum(Pos,N,Sum,L),
    label(L), writeln(L).

el_sum(P,N,Sum,L) :-
    N #> 0,
    M #= N-1,
    Q #= P+1,
    el_sum(Q,M,Sum1,L),
    element(N,L,T),
    Sum #= Sum1 + T.
el_sum(_P,0,0,_L).

yields

?- el_sum(1,2,3).
[0,3,0,0,0]
true ;
[0,3,0,0,1]
true ;
...

Upvotes: 0

false
false

Reputation: 10102

You are mixing here the monotonic world of constraints with some non-monotonic quantification. Don't try to mix them too closely. Instead, first transform those facts into, say, a list of terms.

el_sums(Gs) :-
   G = el_sum(_,_,_),
   findall(G, G, Gs).

And then, only then, start with the constraint part that will now remain monotonic. So:

?- el_sums(Gs), length(L5,5), maplist(l5_(L5), Gs).

l5_(L5, el_sum(P, N, S)) :-
   length([_|Pre], P),
   length(Cs, N),
   phrase((seq(Pre),seq(Cs),seq(_)), L5),
   list_sum(Cs,S).

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

Upvotes: 3

Related Questions