在Prolog中對列表進行分區

Question

我正在嘗試創建一個Prolog謂詞，其中給定一個列表，可以看出列表是否可以拆分成兩個總計爲相同數量的列表。

我有一個工作列表總和謂詞，所以我在分區謂詞中使用它。我首先嚐試對謂詞進行編碼，以查看列表的第一個元素是否等於列表的其餘部分的總和（[2,1,1]）。這就是我對這種情況的看法。

partitionable([X|Y]) :- 
    sum([X],SUM), 
    sum([Y],SUM2), 
    SUM = SUM2. 

不過，我收到此錯誤信息：

ERROR: is/2: Arithmetic: `[]/0' is not a function. 

我想獲得這一塊的工作之前，我深入到遞歸列表的其餘部分，雖然我什麼困惑這條消息是說，因爲我沒有寫過'[]/0' function。任何幫助表示讚賞。

Answer 1

我相信傳遞X作爲[X]是必需的，因爲X只是元素（在你的例子中是2）。另一方面，Y是一個列表本身，不應該放在另一個列表中。 下面是修改的版本：

partitionable([X|Y]) :- sum([X],SUM), sum(Y,SUM2), SUM=SUM2. 
sum([X|Y],SUM) :- sum(Y, SUBSUM), SUM is SUBSUM + X. 
sum([X],SUM) :- X=SUM. 

partitionable([2,1,1])返回true在我的情況。

編輯： 既然你不使用is/2這可能是在sum斷言錯誤。

另一個說明：據我瞭解您的問題，您不需要解決方案partitionable但您收到的錯誤消息。 但是這裏是我對實現它（可能攪局提前）：

/* partitionable(X) 
* If a 2-partition of X exists where both sublists have the same sum, then X 
* is considered partitionable. 
*/ 
partitionable(X) :- partition(X, A, B), sum(A, SUM), sum(B, SUM2), SUM =:= SUM2, !. 

/* partition(X, A, B) 
* X is split in two lists A and B and will, during backtracking, bind A and B to 
* ALL permutations of the list partition, including permutations for each list. 
*/ 
partition([], [], []). 
partition([X|Y], A, B) :- partition(Y, R, B), extract(X, A, R). 
partition([X|Y], A, B) :- partition(Y, A, R), extract(X, B, R). 

/* extract(X, L, R) 
* Extracts exactly one element X from L and unify the result with R. 
*/ 
extract(X, [H|T], R) :- X = H, R = T. 
extract(X, [H|T], R) :- R = [H|R2], extract(X, T, R2). 

sum([X|Y],SUM) :- sum(Y, SUBSUM), SUM is SUBSUM + X. 
sum([X],SUM) :- X = SUM. 

Answer 2

進行分區列表分爲兩個不重疊subsequences， 我們使用list_subseq_subseq/3：

list_subseq_subseq([] ,[] ,[]). 
list_subseq_subseq([X|Xs],[X|Ys],Zs) :- 
    list_subseq_subseq(Xs,Ys,Zs). 
list_subseq_subseq([X|Xs],Ys,[X|Zs]) :- 
    list_subseq_subseq(Xs,Ys,Zs). 

對於執行整數算術，我們使用clpfd：

:- use_module(library(clpfd)). 

讓我們把它放在一起！在下面的示例查詢我們分區列表[1,2,3,4,5,6,7]：

?- Xs = [1,2,3,4,5,6,7], 
    sum(Xs,#=,Total), 
    Half*2 #= Total, 
    list_subseq_subseq(Xs,Ys,Zs), 
    sum(Ys,#=,Half), 
    sum(Zs,#=,Half). 
    Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,2,4,7], Zs = [3,5,6] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,2,5,6], Zs = [3,4,7] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,3,4,6], Zs = [2,5,7] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,6,7] , Zs = [2,3,4,5] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [2,3,4,5], Zs = [1,6,7] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [2,5,7] , Zs = [1,3,4,6] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [3,4,7] , Zs = [1,2,5,6] 
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [3,5,6] , Zs = [1,2,4,7] 
; false. 

Answer 3

我也提供了分區的問題的另一個解決方案。幫助謂詞有助於切割列表兩個列表。例如[1,2,3]可板缺向下：

[1,2]（左側）和[3]（右側）或

[3]（左側）和[1 ，2]（右側）。

helper([],[],[],0,0). 
helper([X|XS],[X|L],R,SUML,SUMR):-helper(XS,L,R,SUMN,SUMR),SUML is SUMN+X. 
helper([X|XS],L,[X|R],SUML,SUMR):-helper(XS,L,R,SUML,SUMN),SUMR is SUMN+X. 
partition(S,L,R):-helper(S,L,R,X,X). 

輸出是：

1 ?- partition([1,2,3,4],L,R). 
L = [1, 4], 
R = [2, 3] ; 
L = [2, 3], 
R = [1, 4] ; 
false. 

Answer 4

也許我underthinking這一點，但...

如果通過「對列表進行分區」，您的意思是「將列表中的列表切分爲兩列，保持順序，而不是創建列表的各種排列），但似乎並不像解決方案那樣比類似的更復雜這樣的：

partitionable(Ns) :- 
    append(Prefix , Suffix , Ns) , 
    compute_sum(Prefix,Sum) , 
    compute_sum(Suffix,Sum) . 

compute_sum(Ns , S) :- compute_sum(Ns,0,S) . 

compute_sum([]  , S , S) . 
compute_sum([N|Ns] , T , S) :- T1 is N+T , compute_sum(Ns,T1,S) . 

如果你想避免使用內置插件，你可以做這樣的事情，其中​​有優雅的增值收益，同時儘量減少列表遍歷：

partitionable(List) :- 
    sum_prefix(List , Sum , Sfx) , 
    sum_prefix(Sfx , Sum , [] ) . 

sum_prefix(List , Sum , Suffix) :- sum_prefix(List,0,Sum,Suffix) . 

sum_prefix(Suffix , Sum , Sum , Suffix) . 
sum_prefix([H|List] , Acc , Sum , Suffix) :- 
    Acc1 is Acc+H , 
    sum_prefix(List,Acc1,Sum,Suffix) 
    . 

Answer 5

它越來越好！

對於非確定性分區列表，如果我們使用正確的元謂詞/謂詞組合，我們不需要實現遞歸輔助謂詞，如list_subseq_subseq/3！

在這個答案，我們使用tpartition/4作爲meta-predicate和 的「物化外卡」謂詞(*)/2傳遞給tpartition/4謂語。 (*)/2可以這樣定義：

_ * true. 
_ * false. 

讓我們把tpartition/4與(*)/2使用和clpfd約束(#=)/2 and sum/3：

?- use_module(library(clpfd)). % use clp(FD) library 
true. 

?- ABs = [1,2,3,4,5,6,7],  % same data as in the earlier answer 
    sum(ABs,#=,NN), 
    N*2 #= NN, 
    tpartition(*,ABs,As,Bs), 
    sum(As,#=,N), 
    sum(Bs,#=,N). 
    NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,2,4,7], Bs = [3,5,6] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,2,5,6], Bs = [3,4,7] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,3,4,6], Bs = [2,5,7] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,6,7] , Bs = [2,3,4,5] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [2,3,4,5], Bs = [1,6,7]  
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [2,5,7] , Bs = [1,3,4,6]  
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [3,4,7] , Bs = [1,2,5,6] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [3,5,6] , Bs = [1,2,4,7] 
; false.