Prolog - How to find the maximum set of elements that their sum is N
SWI-Prolog has a library for programming with constraints in logic. It's called clpfd
.
:-use_module(library(clpfd)).
Let's say that you have a variable for the length of the subsequence. Its scope goes from zero (corresponding to an empty subsequence) to the length of the list. To get the longest sequence first, try the values starting with the highest value.
...
length(List, M),
L in 0..M,
labeling([max(L)],[L]),
...
Next, L
you can use it to build a list of variables L
that will match the indices of the elements from List
. Since these indexes must be in ascending order, chain/2
you can use them to create constraints #</2
between any two consecutive indexes.
...
length(Indices, L),
Indices ins 1..M,
chain(Indices, #<),
...
Using these indices, you can create a list with items from List
. nth1/3
useful here, but with a little trick.
...
nth1a(List, N, E):-
nth1(N, List, E).
...
maplist(nth1a(List), Indices, SubSequence),
...
And the sum of this list should be N
:
...
sum(SubSequence, #=, N)
...
Since only the longest sequence is required, once/1
can be used to stop after finding the first solution.
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.
Since I'm not sure if this is homework or not, I won't post the complete code here.
source to share
In this answer we use clpfd and some lambda:
:- use_module([library(clpfd),
library(lambda)]).
Based meta-predicate maplist/4
and restrictions (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).
Example 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.
source to share