algorithm - Prolog排列

Question

我正在尝试更多地学习序言，因为下学期我将在学校上一门人工智能类(class)。我已经能够掌握基础知识并可以做基于关系的事情，但是，我一直在尝试学习排列和组合电子学，它们看起来很简单，但这让我想到了一个我无法弄清楚的问题怎么解决。假设我想知道 1 和 0 的排列，条件是必须至少有 4 个 1 连续。我不知道从哪里开始尝试为此找到解决方案，但最后我希望代码执行如下操作:

?- placeOnesAndZeros(9,X).
% where 9 is the length of the list/array and X is the permutations

[0,0,0,0,0,0,0,0,0]
[1,1,1,1,0,0,0,0,0]
[0,1,1,1,1,0,0,0,0]
[0,0,1,1,1,1,0,0,0]
[0,0,0,1,1,1,1,0,0]
[0,0,0,0,1,1,1,1,0]
[0,0,0,0,0,1,1,1,1]
[1,1,1,1,0,1,1,1,1]
[1,1,1,1,1,0,0,0,0]
[0,1,1,1,1,1,0,0,0]
[0,0,1,1,1,1,1,0,0]
[0,0,0,1,1,1,1,1,0]
[0,0,0,0,1,1,1,1,1]
[1,1,1,1,1,1,0,0,0]
[0,1,1,1,1,1,1,0,0]
[0,0,1,1,1,1,1,1,0]
[0,0,0,1,1,1,1,1,1]
[1,1,1,1,1,1,1,0,0]
[0,1,1,1,1,1,1,1,0]
[0,0,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,0]
[0,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1]

提前致谢!

编辑代码:

printList([ ]).
printList([H|T]) :- print(H), nl, printList(T).

eval([],_).
eval([H|T],[1,0]):-member(H,[1,0]),eval(T,[1,0]).

placeOnesAndZeros(N, L):-length(L,N), eval(L,[1,0]).

Answer 1

生成和测试 它是用于搜索解决方案空间的基本技术的名称。在 Prolog 中，它实际上是内置的。只需提供一个过滤器来丢弃不需要的内容:

?- placeOnesAndZeros(9,L),once(append(_,[1,1,1,1|_],L)).

once/1 是必需的，否则 append/3 可能会成功多次。为了检查方法的正确性，这里是如何计算我们得到了多少解决方案:

?- aggregate(count,L^H^T^(placeOnesAndZeros(9,L),once(append(H,[1,1,1,1|T],L))),C).
C = 111.

可以使用 aggregate_all 避免对变量 L、H、T(最后两个仅引入聚合)进行量化:

?- aggregate_all(count,(placeOnesAndZeros(9,L),once(append(_,[1,1,1,1|_],L))),C).
C = 111.

编辑

正如@lurker 指出的，我的过滤器不正确。试试看

atLeastFourOnes(L) :- memberchk(1,L), atLeastFourOnes_(L).

atLeastFourOnes_([]).
atLeastFourOnes_([0|L]) :- atLeastFourOnes_(L).
atLeastFourOnes_([1,1,1,1|L]) :- stripOnes(L,R), atLeastFourOnes_(R).

产生

?- placeOnesAndZeros(9,L),atLeastFourOnes(L).
L = [1, 1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 0] ;
L = [1, 1, 1, 1, 1, 1, 1, 0, 0] ;
...

?- aggregate(count,L^(placeOnesAndZeros(9,L),atLeastFourOnes(L)),C).
C = 22.