Prolog: Arrangements of k elements with sum of elements S

Question

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.

Kiblah

Are you working with any numbers, or rather with integers only? – Romberg

Which Prolog processor are you using? SICStus? SWI? – Romberg

Answer 1

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.

Romberg

I try to do this qst but I have this result (length=3,Sum3) :List = [_A,_B,_C], _A in inf..sup, _B in inf..sup, _C in inf..sup ? how I can recover values from inf..sup – Handspring

@AnsPiter try supplying a value instead of a variable in Sum3? To paraphrase your code, you're basically saying, "give me three things that add up to anything." CLP came back with, "here's three things that have any value." This is why repeat gave Zs ins 1..4 and sum(Zs, #=, 7) to constrain the solution space. – Brave

@AnsPiter. Daniel is right. If you use SICStus, do assert(clpfd:full_answer) to ensure the prolog-toplevel shows residual constraints—so you don't get the impression the proof is complete when it is not! – Romberg

@repeat,@Daniel Lyons, thnks – Handspring

Answer 2

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.

Keratosis

What is that when(ground(L), ...) for? Which use cases can profit from this? – Romberg

@Romberg You're absolute right, there is no need of that. – Keratosis

Answer 3

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

Handspring

Keep it simple! With SICStus Prolog 4.3.2, put the library predicates domain/3 and sum/3 to good use: ?- length(Zs,4), domain(Zs,1,4), sum(Zs,#=,7), labeling([],Zs). – Romberg

@Romberg thnx ,but how I can filter the duplicate result like [0,0,0,7] and [0,7,0,0]...? – Handspring

@Romberg maybe no way to avoid duplicate results – Handspring

I did not get that. What do you mean with "maybe no way to avoid duplicate results"? Have you tried ordered/1 (link above)? – Romberg

OK! But why do you write labeling([],List), ordered(List), Res = List ; false and not ordered(List), labeling([],List) and use List throughout? In general, posting constraints before labeling is preferable. – Romberg

@Romberg it's ok now ? – Handspring

Better, yes. But why put the labeling/2 goal before the ordered/1 goal? Here's some good material that explains why doing labeling last is right: github.com/triska/clpfd/blob/master/clpfd.pdf – Romberg

@Romberg I try to put the ordered/1 before the labeling/2 but the result is not filtering – Handspring

Don't just pick any implementation! Stick to the one presented in this answer: https://mcmap.net/q/1927989/-reaching-end-of-list-in-prolog . – Romberg

@Romberg Triska's article is very interesting also CLP(B) – Handspring

Answer 4

I don't think that permutations could be relevant for your problem. Since the sum operation is commutative, the order of elements should be actually irrelevant. So, after this correction

sumList([], 0).
%sumList([H], H) :-
%   number(H).
sumList([H|Tail], R1) :-
   sumList(Tail, R),
   R1 is R+H.

you can just use your predicates

'arrangements of K elements'(Elements, K, Sum, Arrangement) :-
    comb(Elements, K, Arrangement),
    sumList(Arrangement, Sum).

test:

'arrangements of K elements'([1,2,3,4,5,6],3,11,A).
A = [2, 4, 5] ;
A = [2, 3, 6] ;
A = [1, 4, 6] ;
false.

You already know how to use findall/3 to get all lists at once, if you need them.

Denationalize