Search code examples
prolog

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).

Solution

  • 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.