列出列表序言的所有组合

Question

我想在 Prolog 中编写一个谓词，显示 N 元素列表与恰好 M “黑色元素”（b 为黑色，w 表示白色）。

示例查询：

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

我已经写了这个：

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

返回第一个组合 (L = [b, b, w])，但它不显示其他可能性。另外，它有一个无限循环，我不明白为什么。这是痕迹：

[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

感谢您的帮助。

Answer 1

只需将颜色映射black和白色到零附近的小非阴性整数，我们可以
大大减少了我们的实施工作 - 使用有限域约束：

?- use_module(library(clpfd)).

首先，我们绘制四个值， 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].

接下来，我们再次绘制四个值， at大多数两次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].

最后，我们再次绘制四个值，至少两次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

您需要对表示元素数量 (N) 和黑色元素数量 (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).

示例：

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