带条件的序言排列？

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

我知道我应该某处添加条件的烫发功能，但我想不出到底是什么或在哪里写。

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 is abs(A-B), 
      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 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).