有条件的Prolog排列？

Question

我有这个程序来生成一个列表的所有排列。问题是，我只需要生成连续项的绝对差小于或等于3的排列。

[2,7,5] => [2,5,7]和[7,5,2].[2 7 5]是错误的，因为2-7 = -5和|-5| > 3

置换程序：

perm([X|Y],Z):-
    perm(Y,W),
    takeout(X,Z,W).
perm([],[]).

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]):-
    takeout(X,R,S).

permutfin(X,R):-
    findall(P,perm(X,P),R).

我知道我应该在perm函数的某个地方添加条件，但是我不知道写什么或者写在哪里。

Answer 1

编写置换的一种更直观的方法是：

takeout([X|T],X,T).
takeout([H|L],X,[H|T]) :-
    takeout(L,X,T).

其中第一个元素是原始列表，第二个元素是选择的元素，第三个元素是没有该元素的列表。

在这种情况下，置换谓词定义为：

perm([],[]).
perm(L,[E|T]) :-
    takeout(L,E,R),
    perm(R,T).

这也允许尾部递归，这可能意味着在大多数Prolog系统中有一个重要的优化。

现在，为了只生成最多三个连续差的排列，您可以做两件事：

• 简单的方法是生成和测试:在这里，您让Prolog生成一个置换，但只有在满足某个条件时才能接受它。例如： dif3(_)dif3(A，B=T) :- D为abs(Abs)，D为=< 3，dif3(B=T)。 然后定义： perm3(L，R) :- perm(L，R)，dif3(R)。 这种方法并不是很有效:对于指数数量的排列，只有少数是有效的，这意味着要进行大量的计算。例如，如果元素列表是[2,5,7,9]，那么它将生成从[2,9,...]开始的所有排列，而更智能的方法已经可以看到，无论如何也不会生成有效的解决方案。
• 另一种更智能的方法是交错生成和测试。在这里，您只选择具有有效候选的takeout3/4的数字。您可以定义谓词takeout3(L,P,X,T).，其中L是原始列表，P是前一个数字，X是选定的数字，T是结果列表： Takeout3(X=T，P，X，T) :- D为abs(X-P)，D =< 3. takeout3(H=L，N，X，H= T) :- takeout3(L，N，X，T)。 现在，我们可以生成如下排列： perm3([]，[])perm3(L，E= T) :-外卖(L，E，R)，perm3(R，E，T)。perm3([]，_，[])perm3(L，O，E= T) :- takeout3(L，O，E，R)，perm3(R，E，T)。 注意，我们使用两个版本的perm3：perm3/2和perm3/3，第一个版本用于生成第一个元素(使用旧的takeout/3)，而perm3/3用于使用takeout3/4生成置换的其余部分。 这种方法的完整源代码是： 外卖( X，X，T)。外卖(L，X，H= T) :-外卖(L，X，T)Takeout3(X=T，P，X，T) :- D为abs(X-P)，D =< 3. takeout3(H=L，N，X，H= T) :- takeout3(L，N，X，T)。perm3([]，[])perm3(L，E= T) :-外卖(L，E，R)，perm3(R，E，T)。perm3([]，_，[])perm3(L，O，E= T) :- takeout3(L，O，E，R)，perm3(R，E，T)。 使用swipl运行它会提供： - perm3(2,7,5，L)。L= 2，5，7；L= 7，5，2；false。 预期的行为。

Answer 2

这是另一个解决办法。我在takeout中添加了条件，以确保相邻项在彼此之间的3个范围内：

perm([X|Y],Z):-
    perm(Y,W),
    takeout(X,Z,W).
perm([],[]).

check(_,[]).
check(X,[H|_]) :-
    D is X - H,
    D < 4,
    D > -4.

takeout(X,[X|R],R) :-
    check(X,R).
takeout(X,[F|R],[F|S]):-
    takeout(X,R,S),
    check(F,R).