CODEWITHSUNDEEP
listprologcombinationscombinatorics
Laura Aria
Laura Aria

Reputation: 11

Combinations with repetition in prolog that satisfy certain criteria

I'm trying to make a prolog program that generates all combinations (with repetition) of n elements from a list of m elements whose sum is between two given number A and B. I managed to make the program for permutations, but I hvae no idea what should I use for rep_combinations.

Here is the program for permutations:

chech(L,A,B):-
    findall([X1,X2,X3,X4 ], (
        member(X1, L),
        member(X2, L),
        member(X3, L),
        member(X4, L),
        Sum is X1+X2+X3+X4,
        Sum > A,
        Sum < B
    ), Solutions),
    write(Solutions)
.

Upvotes: 1

Views: 469

Answers (1)

gusbro
gusbro

Reputation: 22585

You can sort the items (X1, X2, X3, X4) to form a combination and then get a set of said combinations. E.g:

 chech2(L,A,B):-
    setof(Combination, X1^X2^X3^X4^Sum^(
        member(X1, L),
        member(X2, L),
        member(X3, L),
        member(X4, L),
        Sum is X1+X2+X3+X4,
        Sum > A,
        Sum < B,
        msort([X1,X2,X3,X4 ], Combination)
    ), Solutions),
    write(Solutions).

I just changed the template used as a result of your findall/3 to get the sorted permutation (using msort/2), and changed the findall/3 to setof/3 to remove duplicates.

Note that it is strange that you print the result instead of adding a fourth argument to your procedure to unify the result (and then the caller can print it if it likes to do so).

Upvotes: 2

Related Questions