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