Prolog - How to find the maximum set of elements that their sum is equal to N

Question

my game is about picking the max set of elements from a given list that their sum is N

example : L=[1,1,2,2,3,2,4,5,6], N = 6 , Sub List would be equal to [1,1,2,2]

I need a hint using constraint logic programming.

The solution must be a sub-list of the original list? (you used both "set of elements from" and "sub-list" in your question) — Tudor Berariu, Jan 06 '15 at 17:35
well it's no important let's say that i must put the result in another list and keep the original one ps: the list is always ascendant yes — Amar AttilaZz, Jan 06 '15 at 18:04
Actually... it is important. Even if the list is always in ascending order, it matters. Think about `L=[1, 1, 3, 4, 5]` and `N=7`. — Tudor Berariu, Jan 06 '15 at 18:07
yes your right the , notice that in my game N is even and must be 2 , 4, 6 or 8 . — Amar AttilaZz, Jan 06 '15 at 18:19
Again, the question is "Do you need the solution to be a continuous subsequence of the original list or a collection of elements of it?". If you want an example with an even `N` where you would get different solutions, here you go: `L=[1, 1, 4, 4, 6]`, `N=8`. — Tudor Berariu, Jan 06 '15 at 18:30
for your example i want the solution to be [1,1,6] it's not important to continuous it's can be just a collection — Amar AttilaZz, Jan 06 '15 at 18:35
Please note: [substring](http://en.wikipedia.org/wiki/Substring#Substring) vs. [subsequence](http://en.wikipedia.org/wiki/Subsequence). These notions are unfortunately a bit messed up in English — false, Jan 06 '15 at 18:56
yes here I want a subsequence of my list witch their sum is equal to N ( N is given ) — Amar AttilaZz, Jan 06 '15 at 19:02
My bad... "continuous subsequence" wasn't the best way to refer to a substring. — Tudor Berariu, Jan 06 '15 at 19:29
yes that's it the wanna have the max number of elements on my resulting list — Amar AttilaZz, Jan 06 '15 at 21:17

score 3 · Accepted Answer · answered Jan 06 '15 at 20:18

There is a library for Constrained Logic Programming in SWI-Prolog. It's called clpfd.

:-use_module(library(clpfd)).

Let's say that you'll have a variable for the length of the subsequence. Its domain goes from zero (corresponding to the empty subsequence) to the length of the list. In order to get the longest sequence first, values should be tried starting with the highest.

...
    length(List, M),
    L in 0..M,
    labeling([max(L)],[L]),
...

Next, L can be used to build a list of L variables that would correspond to indices of elements from List. As these indices must be in ascending order, chain/2 can be used to create #</2 constraints between any two consecutive indices.

...
    length(Indices, L),
    Indices ins 1..M,
    chain(Indices, #<),
...

Using these indices, a list with elements from List can be constructed. nth1/3 is useful here, but with a minor trick.

...
nth1a(List, N, E):-
    nth1(N, List, E).
...
    maplist(nth1a(List), Indices, SubSequence),
...

And the sum of that list must be N:

...
    sum(SubSequence, #=, N)
...

As only the longest sequence is needed, once/1 can be used to stop after first solution is found.

Some example queries:

?- longest_subsequence([1,1,4,4,6], 9, S).
S = [1, 4, 4].

?- longest_subsequence([1,1,4,4,6], 11, S).
S = [1, 4, 6].

?- longest_subsequence([1,1,4,4,6], 21, S).
false.

As I am not sure if that's a homework or not, I won't post the full code here.

thank your for this effort, your helping me a lot i'll try to figure out the hole code ;) — Amar AttilaZz, Jan 06 '15 at 21:22

score 1 · Answer 2 · edited May 23 '17 at 11:59

In this answer we use clpfd and a little lambda:

:- use_module([library(clpfd),
               library(lambda)]).

Based on meta-predicate maplist/4 and the constraints (ins)/2 and sum/3 we define:

zs_selection_len_sum(Zs, Bs, L, S) :-
   same_length(Zs, Bs),
   Bs ins 0..1,
   maplist(\Z^B^X^(X #= Z*B), Zs, Bs, Xs),
   sum(Bs, #=, L),
   sum(Xs, #=, S).

Sample queries using labeling/2 with option max/1:

?- zs_selection_len_sum([1,1,4,4,6],Bs,L,8), labeling([max(L)],Bs).
  Bs = [1,1,0,0,1], L = 3
; Bs = [0,0,1,1,0], L = 2
; false.

?- zs_selection_len_sum([1,1,3,4,5],Bs,L,7), labeling([max(L)],Bs).
  Bs = [1,1,0,0,1], L = 3 
; Bs = [0,0,1,1,0], L = 2
; false.

?- zs_selection_len_sum([1,1,2,2,3,2,4,5,6],Bs,L,6), labeling([max(L)],Bs).
  Bs = [1,1,0,1,0,1,0,0,0], L = 4
; Bs = [1,1,1,0,0,1,0,0,0], L = 4
; Bs = [1,1,1,1,0,0,0,0,0], L = 4
; Bs = [0,0,1,1,0,1,0,0,0], L = 3
; Bs = [0,1,0,0,1,1,0,0,0], L = 3
; Bs = [0,1,0,1,1,0,0,0,0], L = 3
; Bs = [0,1,1,0,1,0,0,0,0], L = 3
; Bs = [1,0,0,0,1,1,0,0,0], L = 3
; Bs = [1,0,0,1,1,0,0,0,0], L = 3
; Bs = [1,0,1,0,1,0,0,0,0], L = 3
; Bs = [1,1,0,0,0,0,1,0,0], L = 3
; Bs = [0,0,0,0,0,1,1,0,0], L = 2
; Bs = [0,0,0,1,0,0,1,0,0], L = 2
; Bs = [0,0,1,0,0,0,1,0,0], L = 2
; Bs = [0,1,0,0,0,0,0,1,0], L = 2
; Bs = [1,0,0,0,0,0,0,1,0], L = 2
; Bs = [0,0,0,0,0,0,0,0,1], L = 1
; false.

Prolog - How to find the maximum set of elements that their sum is equal to N

2 Answers2