Solving set partition in Prolog

Question

I am trying to solve set partition problem in prolog. Suppose, set S = {1,3,4,2,5}. Now to partition it such that

L U R = S && L^R = empty

I want to Implement a predicate partition/3 such that ?- partition(S,L,R) succeeds iff L and R are a valid partition of S . For example, partition([1,2,3],L,R) should succeed with answer sub-stitution L = [1,2], R = [3] . I don't want to consider duplicate entries for this problem.

Answer 1

If your problem does not require that sum(L) = sum(R) as usually stated for the Partition Problem, then

partition(S, [ItemL|L], [ItemR|R]):-
  partition1(S, [ItemL|L], [ItemR|R]).

partition1([], [], []).
partition1([Item|S], [Item|L], R):-
  partition1(S, L, R).
partition1([Item|S], L, [Item|R]):-
  partition1(S, L, R).

If the constraint sum(L) = sum(R) holds, this change to partition/3 would work (though quite inefficient):

partition(S, [ItemL|L], [ItemR|R]):-
  partition1(S, [ItemL|L], [ItemR|R]),
  sumlist([ItemL|L], Sum),
  sumlist([ItemR|R], Sum).

Answer 2

This is a case use for append/3 predicate, we just need to shift the argument.

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

This will find all possible ordered partitions of the list, now you need to verify the sum of their members.

Now your predicate partition/3 should be like this:

sumList([], 0).
sumList([Head|Tail], S):- number(Head), sumList(Tail, S1), S is S1 + Head.

partition(L1, L, R):- append(L, R, L1), sumList(L, S), sumList(R, S).

Test:

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

The problem with this answer is that only the ordered partition will be find