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

这也允许 tail-recursion 这意味着在大多数 Prolog 系统中的重要优化。

现在为了仅生成连续差值最多为 3 的排列，您可以做两件事：

最朴素的方式是generate and test：这里你让Prolog生成一个排列，但是你只有在满足某个条件的情况下才接受它。例如：
```
dif3([_]).
dif3([A,B|T]) :-
    D is abs(A-B),
    D =< 3,
    dif3([B|T]).
```
然后定义：
```
perm3(L,R) :-
    perm(L,R),
    dif3(R).
```
这种方法不是很有效：对于指数数量的排列，可能只有少数是有效的，这意味着大量的计算工作。例如，如果元素列表是 [2,5,7,9]，它将生成所有以 [2,9,...] 开头的排列，而更智能的方法可能已经发现无论如何都不会生成有效的解决方案。

另一种更智能的方法是交错生成和测试。在这里，您 select 只有带有 takeout3/4 的数字是有效的候选者。您可以定义谓词 takeout3(L,P,X,T).，其中 L 是原始列表，P 前一个数字，X selected 数字和 T结果列表：

takeout3([X|T],P,X,T) :-
    D is abs(X-P),
    D =< 3.
takeout3([H|L],N,X,[H|T]) :-
    takeout3(L,N,X,T).

现在我们可以生成一个排列如下：

perm3([],[]).
perm3(L,[E|T]) :-
    takeout(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.

生成排列的余数

该方法的完整源代码为：

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

takeout3([X|T],P,X,T) :-
    D is abs(X-P),
    D =< 3.
takeout3([H|L],N,X,[H|T]) :-
    takeout3(L,N,X,T).

perm3([],[]).
perm3(L,[E|T]) :-
    takeout(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).

Prolog 有条件的排列？

Prolog permutations with condition?

algorithm

list

permutation

prolog

conditional-statements