帶條件的序言排列？

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