Partitioning a List in Prolog

Question

I am trying to create a Prolog predicate where, given a list, it is seen whether or not the list can be split into two lists that sum to the same amount.

I have a working list sum predicate, so I am using that within my partitioning predicate. I first tried to code the predicate to see if the first element of the list equals the sum of the rest of the list ([2,1,1]). This is what I have for that situation.

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

However, I am getting this error message:

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

I would like to get this piece working before I delve into the recursion for the rest of the list, though I am confused on what this message is saying, since I have not written a '[]/0' function. Any help is appreciated.

Answer 1

To partition a list into two non-overlapping subsequences, we use 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).

For performing integer arithmetics, we use clpfd:

:- use_module(library(clpfd)).

Let's put it all together! In the following sample query we partition the list [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 2

It keeps getting better!

To non-deterministically partition lists, we don't need to implement a recursive auxiliary predicate like list_subseq_subseq/3 if we employ the right meta-predicate/predicate combination!

In this answer, we use tpartition/4 as the meta-predicate and the "reified wild-card" predicate (*)/2 as the predicate passed to tpartition/4. (*)/2 can be defined like this:

_ * true.
_ * false.

Let's put tpartition/4 to use with (*)/2 and the clpfd constraints (#=)/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.

Answer 3

I would also offer another solution for the partition problem. helper predicate helps to cut the list two list. For example [1,2,3] can be cutted down:

[1,2] (left side) and [3](right side) or

[3] (left side) and [1,2] (right side).

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

Output is :

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

Answer 4

I believe that passing X as [X] is required, since X is just the element (the number 2 in your example). Y on the other hand is a list in itself an should not be put in another list. Here is the modified version:

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]) returns true in my case.

Edit: Since you do not use is/2 this may be an error in the sum predicate.

On another note: As I understand your question you do not require a solution for partitionable but the error message you received. Nonetheless here is my take on implementing it (possibly spoiler ahead):

/* 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 5

Maybe I'm underthinking this, but...

If by "partition the list", you mean "cut the list in two, preserving order, rather than creating various permutations of the list),it doesn't seem like the solution should be any more complex than something like this:

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

If you want to avoid using built-ins, you could do something like this, which has the added benefits of elegance whilst minimizing list traversals:

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