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