CODEWITHSUNDEEP
prolog
Rod
Rod

Reputation: 752

All combinaisons with repetition of a list

Beginner with Prolog, I'm trying to get all the combinations with repetition of all elements in a list. Something like:

combinaisons(NMax, Items) :-
    1 #=< N,
    N #=< NMax,
    combinaisons([item(1,2),item(2,2),item(3,6)], N, Items).

combinaisons(_, 0, []).
combinaisons(Values, N, [Head|Tail]) :-
    length([Head|Tail], N),
    N2 is N - 1,
    member(Head, Values),
    combinaisons(Values, N2, Tail).

The behavior is exactly as I wanted. However Prolog crashes at the end of the execution.

?- combinaisons(2, Items).
Items = [item(1, 2)] ;
Items = [item(2, 2)] ;
Items = [item(3, 6)] ;
Items = [item(1, 2), item(1, 2)] ;
Items = [item(1, 2), item(2, 2)] ;
Items = [item(1, 2), item(3, 6)] ;
Items = [item(2, 2), item(1, 2)] ;
Items = [item(2, 2), item(2, 2)] ;
Items = [item(2, 2), item(3, 6)] ;
Items = [item(3, 6), item(1, 2)] ;
Items = [item(3, 6), item(2, 2)] ;
Items = [item(3, 6), item(3, 6)] ;
ERROR: Out of global-stack.
ERROR: No room for exception term.  Aborting.
ERROR: Out of global-stack.
ERROR: No room for exception term.  Aborting.
Could not reenable global-stack
Could not reenable global-stack
Could not reenable global-stack
% Execution Aborted

Works great for values with values N < 2

?- combinaisons(1, Items). 
Items = [item(1, 2)] ;
Items = [item(2, 2)] ;
Items = [item(3, 6)] ;
false.

?- combinaisons(0, Items). 
false.

What is my mistake in this code?

-

Bonus: How to simplify [item(1,2),item(2,2),item(3,6)] if i have

item(1,2).
item(2,2).
item(3,6).

Upvotes: 0

Views: 53

Answers (1)

peter.cyc
peter.cyc

Reputation: 1813

The comparators #=< are used as numerical constraints on N, but there is no need: it can be replaced by enumerating 1..Max as done in cc1/3. I'm using SWI-Prolog:

combinaisons(NMax, Items) :-
    cc1(1, NMax, Items).
    
    cc1(N, NMax, Items) :- 
        N > NMax, !.
    cc1(N, NMax, Items) :-  
        combinaisons([item(1,2),item(2,2),item(3,6)], N, Items).
    cc1(N, NMax, Items) :-  
        N1 is N+1,
        cc1(N1, NMax, Items).

    combinaisons(_, 0, []).
    combinaisons(Values, N, [Head|Tail]) :-
        length([Head|Tail], N),
        N2 is N - 1,
        member(Head, Values),
        combinaisons(Values, N2, Tail).

The result is:

?- combinaisons(2, Items) .
Items = [item(1, 2)] ;
Items = [item(2, 2)] ;
Items = [item(3, 6)] ;
Items = [item(1, 2), item(1, 2)] ;
Items = [item(1, 2), item(2, 2)] ;
Items = [item(1, 2), item(3, 6)] ;
Items = [item(2, 2), item(1, 2)] ;
Items = [item(2, 2), item(2, 2)] ;
Items = [item(2, 2), item(3, 6)] ;
Items = [item(3, 6), item(1, 2)] ;
Items = [item(3, 6), item(2, 2)] ;
Items = [item(3, 6), item(3, 6)] ;
true.

Upvotes: 1

Related Questions