List all combinations of a list prolog

Question

I want to write in Prolog a predicate that display all the combinations of a list of N elements with exactly M "black elements" (b for black and w for white).

Sample query:

?- combination(3, 2, L).
L = [b, b, w] ;
L = [b, w, b] ;
L = [w, b, b] ;
false.

I've written this:

combination(0, _, []).
combination(Nn, 0, [w|L]) :-
   NN1 is Nn-1,
   combination(NN1, 0, L).
combination(Nn, N, [b|L]) :-
   N1 is N-1,
   NN1 is Nn-1,
   combination(NN1, N1, L).
combination(Nn, N, [w|L]) :-
   NN1 is Nn-1,
   combination(NN1, N, L).

that returns me the first combination (L = [b, b, w]), but it don't display other possibilities. Also, it has an infinite loop, I don't understand why. Here is the trace:

[trace]  ?- combination(3, 2, L).
   Call: (10) combination(3, 2, _2900) ? creep
   Call: (11) _4108 is 2+ -1 ? creep
   Exit: (11) 1 is 2+ -1 ? creep
   Call: (11) _5624 is 3+ -1 ? creep
   Exit: (11) 2 is 3+ -1 ? creep
   Call: (11) combination(2, 1, _4100) ? creep
   Call: (12) _7904 is 1+ -1 ? creep
   Exit: (12) 0 is 1+ -1 ? creep
   Call: (12) _9420 is 2+ -1 ? creep
   Exit: (12) 1 is 2+ -1 ? creep
   Call: (12) combination(1, 0, _7896) ? creep
   Call: (13) _11700 is 1+ -1 ? creep
   Exit: (13) 0 is 1+ -1 ? creep
   Call: (13) combination(0, 0, _11692) ? creep
   Exit: (13) combination(0, 0, []) ? creep
   Exit: (12) combination(1, 0, [w]) ? creep
   Exit: (11) combination(2, 1, [b, w]) ? creep
   Exit: (10) combination(3, 2, [b, b, w]) ? creep
L = [b, b, w] ;
   Redo: (13) combination(0, 0, _11692) ? creep
   Call: (14) _19114 is 0+ -1 ? creep
   Exit: (14) -1 is 0+ -1 ? creep
   Call: (14) combination(-1, 0, _19106) ? creep
   Call: (15) _21394 is -1+ -1 ? creep
   Exit: (15) -2 is -1+ -1 ? creep

Thanks for your help.

Answer 1

Simply by mapping the colors black and white to small non-negative integers around zero, we can greatly reduce our implementation effort—by using finite domain constraints:

?- use_module(library(clpfd)).

First, we draw four values, exactly two times 1:

?- length(Xs,4), Xs ins 0..1, sum(Xs,#=,2), labeling([],Xs).
   Xs = [0,0,1,1]
;  Xs = [0,1,0,1]
;  Xs = [0,1,1,0]
;  Xs = [1,0,0,1]
;  Xs = [1,0,1,0]
;  Xs = [1,1,0,0].

Next, we again draw four values, at most two times 1:

?- length(Xs,4), Xs ins 0..1, sum(Xs,#=<,2), labeling([],Xs).
   Xs = [0,0,0,0]
;  Xs = [0,0,0,1]
;  Xs = [0,0,1,0]
;  Xs = [0,0,1,1]
;  Xs = [0,1,0,0]
;  Xs = [0,1,0,1]
;  Xs = [0,1,1,0]
;  Xs = [1,0,0,0]
;  Xs = [1,0,0,1]
;  Xs = [1,0,1,0]
;  Xs = [1,1,0,0].

Last, we again draw four values, at least two times 1:

?- length(Xs,4), Xs ins 0..1, sum(Xs,#>=,2), labeling([],Xs).
   Xs = [0,0,1,1]
;  Xs = [0,1,0,1]
;  Xs = [0,1,1,0]
;  Xs = [0,1,1,1]
;  Xs = [1,0,0,1]
;  Xs = [1,0,1,0]
;  Xs = [1,0,1,1]
;  Xs = [1,1,0,0]
;  Xs = [1,1,0,1]
;  Xs = [1,1,1,0]
;  Xs = [1,1,1,1].

Answer 2

You need additional constraints on the values of the variables denoting number of elements (N) and number of black elements (B).

combination(0, _, []).
combination(N, 0, [w|L]) :- N > 0, N1 is N-1, combination(N1, 0, L).
combination(N, B, [b|L]) :- N >= B, B > 0, N1 is N-1, B1 is B-1, combination(N1, B1, L).
combination(N, B, [w|L]) :- N > B, B > 0, N1 is N-1, combination(N1, B, L).

Examples:

?- combination(3, 2, L).
L = [b, b, w] ;
L = [b, w, b] ;
L = [w, b, b] ;
false.

?- combination(4, 2, L).
L = [b, b, w, w] ;
L = [b, w, b, w] ;
L = [b, w, w, b] ;
L = [w, b, b, w] ;
L = [w, b, w, b] ;
L = [w, w, b, b] ;
false.