1

I'm trying to achieve an old exercice from my school and i can't figure it out how to solve it. Here is the result expected :

bC([1,12,34,23,11],23,Res).

Res = 1+11-12+23

So bC/3 is supposed to find every combination of addition or substract operation (the third argument) from a list of number (the first argument) to match a result (the second argument).

I can't find a way to start resolving this... If someone could give me a clue about this problem, i would really appreciate it.

UPDATE: Some elements of the list can be left out.

false
  • 10,264
  • 13
  • 101
  • 209
ldeniau
  • 35
  • 5

1 Answers1

0

As a hint: you can aim to construct all expressions by exhautively searching over the expression space. Since X - (Y - Z) is just X - Y + Z, this is good news, since we can restrict us to left recursive expressions, like:

makepm([], ExpI, ExpI).
makepm([H|T], ExpI, ExpO) :-
    makepm(T, +(ExpI, H), ExpO).
makepm([H|T], ExpI, ExpO) :-
    makepm(T, -(ExpI, H), ExpO).

If as first element we take 1, and we inject the rest of the list in the makepm/3, we get:

?- makepm([12,34,23,11], 1, F).
F = 1+12+34+23+11 ;
F = 1+12+34+23-11 ;
F = 1+12+34-23+11 ;
F = 1+12+34-23-11 ;
F = 1+12-34+23+11 ;
F = 1+12-34+23-11 ;
F = 1+12-34-23+11 ;
F = 1+12-34-23-11 ;
F = 1-12+34+23+11 ;
F = 1-12+34+23-11 ;
F = 1-12+34-23+11 ;
F = 1-12+34-23-11 ;
F = 1-12-34+23+11 ;
F = 1-12-34+23-11 ;
F = 1-12-34-23+11 ;
F = 1-12-34-23-11.

What still needs to be done: the question is not perfectly clear about the fact if numbers can be left out, if that is the case, then you should write a predicate that first selects a subset of numbers. Then we can exhaustively enumerate all expressions which we create with makepm/3, and then we need to verify, for example with the is/2 [swi-doc] predicate that the expression sums up to the requested value. If that is the case the predicate can succeed.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • 1
    That's a very good hint :). I will try to use your predicate with what i've found here https://stackoverflow.com/questions/4578755/permuted-combinations-of-the-elements-of-a-list-prolog to get all possible permuted combination. I begin to understand how i have to think to resolve this kind of problems now... – ldeniau Sep 23 '18 at 11:18