I am trying to compute arrangements of K
elements in Prolog, where the sum of their elements is equal to a given S
. So, I know that arrangements can be computed by finding the combinations and then permute them. I know how to compute combinations of K
elements, something like:
comb([E|_], 1, [E]).
comb([_|T], K, R) :-
comb(T, K, R).
comb([H|T], K, [H|R]) :-
K > 1,
K1 is K-1,
comb(T, K1, R).
The permutations of a list, having the property that the sum of their elements is equal to a given S, I know to compute like this:
insert(E, L, [E|L]).
insert(E, [H|T], [H|R]) :-
insert(E, T, R).
perm([], []).
perm([H|T], P) :-
perm(T, R),
insert(H, R, P).
sumList([], 0).
sumList([H], H) :-
number(H).
sumList([H|Tail], R1) :-
sumList(Tail, R),
R1 is R+H.
perms(L, S, R) :-
perm(L, R),
sumList(R, S1),
S = S1.
allPerms(L, LP) :-
findall(R, perms(L,R), LP).
The problem is that I do not know how to combine them, in order to get the arrangements of K
elements, having the sum of elements equal to a given S
. Any help would be appreciated.
Use clpfd!
:- use_module(library(clpfd)).
Using SWI-Prolog 7.3.16 we query:
?- length(Zs,4), Zs ins 1..4, sum(Zs,#=,7), labeling([],Zs). Zs = [1,1,1,4] ; Zs = [1,1,2,3] ; Zs = [1,1,3,2] ; Zs = [1,1,4,1] ; Zs = [1,2,1,3] ; Zs = [1,2,2,2] ; Zs = [1,2,3,1] ; Zs = [1,3,1,2] ; Zs = [1,3,2,1] ; Zs = [1,4,1,1] ; Zs = [2,1,1,3] ; Zs = [2,1,2,2] ; Zs = [2,1,3,1] ; Zs = [2,2,1,2] ; Zs = [2,2,2,1] ; Zs = [2,3,1,1] ; Zs = [3,1,1,2] ; Zs = [3,1,2,1] ; Zs = [3,2,1,1] ; Zs = [4,1,1,1].
To eliminate "redundant modulo permutation" solutions use chain/2
:
?- length(Zs,4), Zs ins 1..4, chain(Zs,#=<), sum(Zs,#=,7), labeling([],Zs). Zs = [1,1,1,4] ; Zs = [1,1,2,3] ; Zs = [1,2,2,2] ; false.
I use SWI-Prolog. You can write that
:- use_module(library(lambda)).
arrangement(K, S, L) :-
% we have a list of K numbers
length(L, K),
% these numbers are between 1 (or 0) and S
maplist(between(1, S), L),
% the sum of these numbers is S
foldl(\X^Y^Z^(Z is X+Y), L, 0, S).
The result
?- arrangement(5, 10, L).
L = [1, 1, 1, 1, 6] ;
L = [1, 1, 1, 2, 5] ;
L = [1, 1, 1, 3, 4] ;
L = [1, 1, 1, 4, 3] .
You can use also a CLP(FD) library.
Edited after the remark of @repeat.
This response is similar to response of @repeat
predicates that below are implemented using the SICStus 4.3.2 tool
after simple modification of gen_list(+,+,?)
edit Code
gen_list(Length,Sum,List) :- length(List,Length),
domain(List,0,Sum),
sum(List,#=,Sum),
labeling([],List),
% to avoid duplicate results
ordered(List).
Test
| ?- gen_list(4,7,L).
L = [0,0,0,7] ? ;
L = [0,0,1,6] ? ;
L = [0,0,2,5] ? ;
L = [0,0,3,4] ? ;
L = [0,1,1,5] ? ;
L = [0,1,2,4] ? ;
L = [0,1,3,3] ? ;
L = [0,2,2,3] ? ;
L = [1,1,1,4] ? ;
L = [1,1,2,3] ? ;
L = [1,2,2,2] ? ;
no
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With